image.png
class Solution {
public:
static bool cmp(vector<int>&a,vector<int>&b){
// end从小到大,相同条件begin从大到小
return a[1]<b[1];
}
vector<vector<int>> merge(vector<vector<int>>& intervals) {
vector<vector<int>>res;
if(intervals.size()==0){
return res;
}
sort(intervals.begin(),intervals.end(),cmp);
res.push_back(intervals[0]);
for(int i=1;i<intervals.size();i++){
while(res.size()>0&&res.back()[0]>=intervals[i][0]){
// pre内含于now [1,2],[3,4],[1,4] =>[1,4] / [3,4],[2,6] =>[2,6]
// 需要pop所有内含型pre,避免遗漏,当然这些pre对结果也无影响
res.pop_back();
}
if(res.size()==0){
res.push_back(intervals[i]);
}
else{
if(res.back()[1]>=intervals[i][0]&&res.back()[0]<=intervals[i][0]){
// 交叉型 [2,4],[3,5]=>[2,5]
// vector<int>v{res.back()[0],intervals[i][1]};
// res.pop_back();
// res.push_back(v);
res.back()[1]=intervals[i][1];
}
else{
// 分离型 [1,3],[4,6] =>[1,3],[4,6]
res.push_back(intervals[i]);
}
}
}
return res;
}
};
