[56]合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 $intervals[i] = [start_i, end_i]$

请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]

输出：[[1,6],[8,10],[15,18]]

解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

[57] 插入区间

给你一个无重叠的，按照区间起始端点排序的区间列表 intervals，其中$ intervals[i] = [start_i, end_i] $表示第 i个区间的开始和结束，并且 intervals 按照 $start_i $升序排列。同样给定一个区间 $newInterval = [start, end]$表示另一个区间的开始和结束。

在 intervals 中插入区间 newInterval，使得 intervals 依然按照 $start_i$升序排列，且区间之间不重叠（如果有必要的话，可以合并区间）,返回插入之后的 intervals。

注意你不需要原地修改 intervals。你可以创建一个新数组然后返回它。

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

输出：[[1,5],[6,9]]

METHOD

注意[56]没有说区间的排序，因此需要先排序：

1	intetvals.sort(key=lambda x:x[0])

现在二者都是按照区间起始端点排序得到的结果了

思路如下：

我们对区间进行依次的遍历，只要前一个区间的尾部小于后一个区间的头部，就证明这个前一个区间是可以直接加入到ans数组中的

对于重叠的部分(即前一个区间的尾部大于等于后一个区间的头部)：把ans数组最后一个的右边界扩展为重叠部分的最大值即可，即右边界和重叠区间的右边界的最大值

只有这两种情况

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        ans = []
        # lambda x: x是一个匿名函数，对列表中的每个元素应用这个函数，取每个元素的第一个子元素作为排序依据
        intervals.sort(key=lambda x: x[0])
        for i in range(len(intervals)):
            if not ans or intervals[i][0] > ans[-1][1]:
                ans.append(intervals[i])
            else:
                ans[-1][1] = max(ans[-1][1], intervals[i][1])
        return ans

对插入来说，这里可以先插入排序，再规约到重叠区间的问题上，但是复杂度为O(logn)

插入有自己的办法:我们还是遍历区间

首先，如果插入区间的左边界小于当前区间的右边界，证明该区间可以直接加入
其次，如果插入区间的右边界大于当前区间的左边界，该区间也可以直接插入
- 注意这里必须是在把重叠边界已经插入的情况下
都不满足：我们需要更新当前的重叠边界，左边更新为插入区间和左边边界的最小值，右边更新为插入区间和右边边界的最大值
- 用placed判断是否该重叠边界已经插入

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        ans = []
        left = newInterval[0]
        right = newInterval[1]
        placed = False
        for i in range(len(intervals)):
            if intervals[i][1] < newInterval[0]:
                ans.append(intervals[i])
            elif intervals[i][0] > newInterval[1]:
                # 这个解决了重叠区间在左边的情况，placed的判断非常有用
                # 到右边区间之前先把这个区间加进去，包括在所有区间之前的情况
                if not placed:
                    ans.append([left, right])
                    placed = True
                ans.append(intervals[i])
            else:
                left = min(left, intervals[i][0])
                right = max(right, intervals[i][1])
        # 这个解决在所有区间之后的情况
        if not placed:
            ans.append([left, right])
        return ans

Resume

区间合并和插入