57. 插入区间

题目描述

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

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

示例 1：

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

示例 2：

1
2
3
输入：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] 重叠。

注意：输入类型已在 2019 年 4 月 15 日更改。请重置为默认代码定义以获取新的方法签名。

思路

模拟

  • 判断newInterval是否和interval有重叠

    • 有，进行合并，之后更新的newInterval（不需要插入interval）

    • 没有，判断newInterval是否可以插入

      • 可以，插入newInterval，之后插入interval

      • 不可以，插入interval

  • 合并条件：区间之间存在交叉，interval[1] >= newInterval[0] \&\& interval[0] <= newInterval[1]

  • image-20201104093554022

  • 插入条件：新区间的尾端小于interval的起点，但是可能会插入很多次，因此需要打标记。newInterval[1] < interval[0]&&!flag。

    C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> res;
        bool flag = false;
        // interval和newInterval合并，不能合并就插入
        for(const auto& interval:intervals) {
            // 重合
            if(interval[1] >= newInterval[0] && interval[0] <= newInterval[1]) {
                newInterval[0] = min(newInterval[0], interval[0]);
                newInterval[1] = max(newInterval[1], interval[1]);
                continue;
            } else if(newInterval[1] < interval[0] && !flag) {
                // 不重合, 且是第一次
                res.push_back(newInterval);
                flag = true;
            }
            res.push_back(interval);
        }
        if(!flag) {
            res.push_back(newInterval);
        }
        return res;
    }
};