题目描述
Given a collection of intervals, merge all overlapping intervals.
Example1:
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].
Example2:
Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
Note:
input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.
解题思路
- 这一题首先要进行排序操作，要求每个vector第一个表示是升序操作
- 按题意，分为几种情况
-
- 循环从 0 - > size - 1 // 因为中间会改变 i + 1 的值，这样只需要在最后面将改变后的值给追加进行即可
-
- 如果 intervals[i][1] < intervals[i + 1][0] 即 [1,6],[8,10] 的情况 // 不能合并的情况，直接push到最后的结果即可
-
- 如果 intervals[i][1] >= intervals[i + 1][0] && intervals[i][1] < intervals[i + 1][1] // 可以合并的情况，需要满足 [1,3],[2,6] 即可, 这样 给 intervals[i + 1][0] 赋值即可
-
- 剩余的就是 [1,12], [3,4] 这种 // 这样 需要给 intervals[i + 1][0]， intervals[i + 1][1] 赋值
- 最后记得要把循环条件结束时，把改变后的 最后一个元素 push 进去即可
-
class Solution {
public:
static bool cmp(vector<int>& vec1, vector<int>& vec2){ // 对vector<vector<int>> 进行排序，则形参为里面解除一层的vector<int>引用
return vec1[0] < vec2[0];
}
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if(intervals.size() == 0){
return {};
}
vector<vector<int>> res;
sort(intervals.begin(), intervals.end(), cmp);
int i = 0;
while(i < intervals.size() - 1){
if(intervals[i][1] < intervals[i + 1][0]){
res.push_back(intervals[i]);
}else if(intervals[i][1] >= intervals[i + 1][0] && intervals[i][1] < intervals[i + 1][1]){
intervals[i + 1][0] = intervals[i][0];
}else{
intervals[i + 1][0] = intervals[i][0];
intervals[i + 1][1] = intervals[i][1];
}
++i;
}
res.push_back(intervals[i]);
return res;
}
};
