题目内容

给你一个 无重叠的 ，按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

示例

示例 1：

输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
输出：[[1,5],[6,9]]
示例 2：

输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出：[[1,2],[3,10],[12,16]]
解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。
示例 3：

输入：intervals = [], newInterval = [5,7]
输出：[[5,7]]
示例 4：

输入：intervals = [[1,5]], newInterval = [2,3]
输出：[[1,5]]
示例 5：

输入：intervals = [[1,5]], newInterval = [2,7]
输出：[[1,7]]

提示

1、0 <= intervals.length <= 10^4
2、intervals[i].length == 2
3、0 <= intervals[i][0] <= intervals[i][1] <= 10^5
4、intervals 根据intervals[i][0]按 升序 排列
5、newInterval.length == 2
6、0 <= newInterval[0] <= newInterval[1] <= 10^5

题解

本题是对合并区间的扩展应用。要求解本题，需要考虑三个情况，即：

1、可能存在的靠左区间完全与新区间没有交集的部分

2、可能存在的中间区间与新区间有交集的部分

3、可能存在的右边区间与新区间没有交集的部分

画图如下所示：

因此，仅仅需要将三个部分找出来，然后进行处理即可。

第一部分满足，遍历区间的右端点大于需要合并的区间的左端点

第三部分，满足需要合并的区间的右端点小于遍历区间的左端点

第二部分，需要确定交集的情况，求出遍历和合并区间的左端点的全局最小值，求出遍历和合并区间的右端点的全局最大值，然后生成新的区间，并将原有的区间内部的区间替换为当前求出的区间即可。

具体实现，请参考代码注释。

代码

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& a, vector<int>& b) {
        //分成三部分考虑，第一部分是左边与新区间完全没有交集的部分，第二部分是中间与新区间有交集的部分，第三部分是右边完全与新区间完全没有交集的部分。
        vector<vector<int>> res;
        int k = 0;
        while(k < a.size() && a[k][1] < b[0])res.push_back(a[k++]);//左边完全完全没有交集的部分
        if(k < a.size()){
            //根据大小关系判断并确定b的左右端点
            b[0] = min(b[0],a[k][0]);
            while(k < a.size() && a[k][0] <= b[1]) b[1] = max(b[1],a[k++][1]);
        }
        res.push_back(b);//将b添加到答案中

        while(k < a.size())res.push_back(a[k++]);//右边完全没有交集的部分
        
        return res;
    }
};