题目描述

给出一列互不相交的区间，现在要输入一个新区间（如果区间发生重叠，需要进行合并操作）。
初始区间已经按左端点从小到大排好序。

样例1

输入：初始区间集合 = [[1, 3], [6, 9]], 新区间 = [2, 5]
输出：[[1, 5], [6, 9]]

样例2

输入：初始区间集合 = [[1,2],[3,5],[6,7],[8,10],[12,16]], 新区间 = [4, 8]
输出：[[1,2],[3,10],[12,16]]
解释：新区间 [4, 8] 与 [3,5],[6,7],[8,10] 有重叠，所以要将它们合并。

算法

(时间复杂度) $O(n)$

用两个指针l，r来表示intervals中与newInterval区间重叠的元素范围：
1. l<len&&intervals[l][1]<newInterval[0] 表示l元素与newInterval不重叠，l++；
2. r<len&&intervals[r][0]<=newInterval[1] 表示r元素与newInterval重叠，r++；
3. 综上所述，重叠的元素范围为[l,r）;
4. 当l==r时，说明没有元素重叠，此时直接插入；
5. 当l！=r时，先去掉重叠的元素，再插入合并之后的元素；

C++ 代码

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int l=0,r=0,len=intervals.size();
        while(l<len&&intervals[l][1]<newInterval[0])l++;
        while(r<len&&intervals[r][0]<=newInterval[1])r++;
        if(l<r){
            vector<int> temp={min(intervals[l][0],newInterval[0]),max(intervals[r-1][1],newInterval[1])};
            intervals.erase(intervals.begin()+l,intervals.begin()+r);
            intervals.insert(intervals.begin()+l,temp);
        }
        else
            intervals.insert(intervals.begin()+l,newInterval);
        return intervals;
    }
};