Description
Given a collection of intervals, merge all overlapping intervals.
给出若干闭合区间，合并所有重叠的部分。
Examples
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Answer
First sort the input in ascending order then traverse the input and compare all the intervals with the biggest/smallest intrerval. if has cross part then modify. if not then push the interval into the result set.
Time Complexity
O(n)
Code
C++
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals)
{
if(intervals.size() == 0 || intervals[0].size() <= 1) return inetervals;
vector<vector<int>> res;
sort(intervals.begin(), intervals.end());
res.push_back(intervals[0]);
for(int i = 0; i < n; ++i)
{
if(intervals[i][0] <= res.back()[1])
res.back()[1] = max(intervals[i][1], res.back()[1]);
else
res.push_back(intervals[i]);
}
return res;
}
};
