Leetcode第57题(插入区间)

题目描述:

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

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

示例 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]]

跟上一题56题合并区间思路一样, 在排序之前将新区间插入到区间集合之中即可, 这儿就不过多赘述了。

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> ans;
        intervals.push_back(newInterval);
        sort(intervals.begin(),intervals.end());
        int start = intervals[0][0],
        end = intervals[0][1];
        for(int i = 1;i < intervals.size();i++){
            if(intervals[i][0] > end){
                ans.push_back({start,end});
                start = intervals[i][0];
                end = intervals[i][1];
            }else{
                end = max(end,intervals[i][1]);
            }
        }
        ans.push_back({start,end});

        return ans;
    }
};

因为原有区间集合是有序并且不重叠的，那么只需要将插入区间插入到正确的位置并将重叠部分合并即可。先将区间集合分成三部分，第一部分是 左边 与插入区间不重叠的部分，第二部分是与插入区间重叠的部分，第三部分是 右边 与插入区间不重叠的部分。

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& a, vector<int>& b) {
        vector<vector<int>> ans;
        int n = a.size(),i = 0;
        //将左侧区间添加至结果(与插入区间不重叠的左侧区间)
        while(i < n && a[i][1] < b[0]){  //左侧区间end < 插入区间左侧
            ans.push_back(a[i++]);
        }
        //处理中间区间(与插入区间重叠的区间)
        if(i < n){
            b[0] = min(b[0],a[i][0]);
            while(i < n && a[i][0] <= b[1]){
                b[1] = max(b[1],a[i++][1]);
            }
        }
        ans.push_back(b);
        //处理后面的区间(与插入区间不重叠的右侧区间)
        while(i < n){
            ans.push_back(a[i++]);
        }

        return ans;
    }
};