题目链接
难度： 困难       类型：数组

示例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] 重叠。

解题思路

需要插入的区间为[s,e]
原区间被分为三部分：
左边：区间的end小于s
右边：区间的start大于e
重叠：最小的start和最大的end

代码实现

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        s = newInterval[0]
        e = newInterval[1]
        left, right = [], []
        for inter in intervals:
            if s>inter[1]:
                left.append(inter)
            elif e<inter[0]:
                right.append(inter)
            else:
                s = min(s, inter[0])
                e = max(e, inter[1])
        return left + [[s, e]] + right