57. 插入区间

Difficulty
Medium
Tags
扫描线
URL
https://leetcode-cn.com/problems/insert-interval/
Star
给你一个 无重叠的 ，按照区间起始端点排序的区间列表。
在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
示例 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]
解释：这是因为新的区间[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]]
提示：
  • 0 <= intervals.length <= 104
  • intervals[i].length == 2
  • 0 <= intervals[i][0] <= intervals[i][1] <= 105
  • intervals 根据 intervals[i][0] 按 升序 排列
  • newInterval.length == 2
  • 0 <= newInterval[0] <= newInterval[1] <= 105
通过次数83,410提交次数203,182

法1 扫描线

思路
此题当然可以先将 intervals newInterval合并，然后按照上一题的方法实现，但是无疑增加了时间复杂度，因为本体intervals 是已经排好序的，所以只需要遍历一遍intervals，在遍历的时候判断新来的区间该怎么插进去即可。总共有如下三种情况：
  1. case1 new[0] > cur[1]
notion imagenotion image
此时，cur区间为独立区间，直接加到res 即可。然后继续遍历完intervals
  1. case 2 cur[0] > new[1]
notion imagenotion image
因为intervals是已经排好序的，所以如果出现这种情况，说明新来的区间和原先的区间均无重合，直接先将New添加到res中，再将cur及剩下的加进去，返回res即可
  1. case 3 除上述两种之外的
notion imagenotion image
共有如上四种情况，当然不用单独分析，因为合并的结果是一样的：
new[0] = min(nw[0],  cur[0]) new[1] = max(new[1],  cur[1])
合并完之后，再用新的new 和剩下的区间比对，切记最后要将new加到res中
题解
class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        if len(intervals) == 0:
            return [newInterval]
        res = []
        for cur in intervals:
            if cur[1] <newInterval[0]:
                res.append(cur)
            elif cur[0] > newInterval[1]:
                # 先将 new加进去，再将cur及其后续的区间加进去
                res.append(newInterval)
                temp = intervals.index(cur)
                res += intervals[temp:]
                return res
            else:
                newInterval[0] = min(cur[0], newInterval[0])
                newInterval[1] = max(cur[1], newInterval[1])
        res.append(newInterval)
        return res