区间并集

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;
    }
};