😄56.合并区间
给出一个区间的集合，请合并所有重叠的区间。
示例 1:
- 输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
- 输出: [[1,6],[8,10],[15,18]]
- 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
- 输入: intervals = [[1,4],[4,5]]
- 输出: [[1,5]]
- 解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
- 注意：输入类型已于2019年4月15日更改。 请重置默认代码定义以获取新方法签名。
思路
基本思想
一旦两个区间出现重叠，就将其合并，合并之后的新区间与后面的区间进行比较
由于区间是乱序存放的，所以需要先进行排序，这样遍历时才会取出相邻的区间
与
452
与
435
思路类似
执行流程
- 对集合进行排序
- 判断flag是否与当前区间重叠，重叠之后合并成新的flag
- 不重叠更新flag，直到遍历结束
代码
根据以上分析，得出以下代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
//先进行排序
sort(intervals.begin(),intervals.end(),[](vector<int>& v1,vector<int>& v2){
if(v1[0]==v2[0])
return v1[1]<v2[1];
return v1[0]<v2[0];
});
//从第一个区间开始判断
vector<int> flag=intervals[0];
//初始时结果容器为空
vector<vector<int>> res;
for(int i=1;i<intervals.size();++i){
//出现重叠更新
if(intervals[i][0]<=flag[1]){
//更新右边界即可,取max是为了防止出现真子集的情况
flag[1]=max(intervals[i][1],flag[1]);
}
//没有出现重叠，需要更新flag和res
else{
res.push_back(flag);
flag=intervals[i];
}
}
//最后一个区间不要忘记，dan'du'c
res.push_back(flag);
return res;
}
};
|
总结
主要是模拟合并的过程，出现重叠就合并，没有重叠就把当前区间加入结果集
遍历到最后一个区间，不管是合并还是不合并，都需要单独将其合并到结果集，因为代码判断的逻辑是不重叠才加入结果集，然后才更新flag，所以最后一个flag无法加入结果集，需要单独处理