leetcode57. 插入区间

分析

所有区间都是有序的，每个区间与合并区间有三种关系：
1. 在区间左边
2 在区间右边
3 在区间中间，即有交集

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) { 
            vector<vector<int>>ans;
            bool flag=false;
            for(int i=0;i<intervals.size();i++){
                int l=intervals[i][0],r=intervals[i][1];
                if(newInterval[0]>r){//在左边
                    ans.push_back(intervals[i]);
                }else if(newInterval[1]<l){//在右边，在右边之后，所有区间都不可能再产生交集，此时替换区间
                        if(!flag){
                            ans.push_back({newInterval});
                            flag=true;
                        }
                    ans.push_back(intervals[i]);
                }else {//在中间，有交集
                    newInterval[0]=min(newInterval[0],l);
                    newInterval[1]=max(newInterval[1],r);
                }
            }
            if(!flag){//所有区间都在左边的话，就将这个新区间加进去
                    ans.push_back(newInterval);
                }
            return ans;
    }
};