56. 合并区间
以数组
intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]] 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：
输入：intervals = [[1,4],[4,5]] 输出：[[1,5]] 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
提示：
1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti<= endi<= 104
法1 扫描线
思路
将intervals 按照开始时间顺序升序排列，这样只有一种情况会有重叠区间：
next[0] ≤ cur[1].如下图
a b 有重叠区间，因为 b[0] <a[1]
b c 有折叠区间，因为c[0] <b[1]
如果当前区间和下一个区间重合，那么将当前区间和下一个区间扩大，再和下下一个区间做对比：
如果当前区间和下一个区间没有重合，那么将当前区间加到res中，再将下一个区间变为当前，好和下下一个比较。
题解
class Solution: def merge(self, intervals: List[List[int]]) -> List[List[int]]: if len(intervals) == 1: return intervals res = [] intervals.sort(key = lambda x:(x[0],x[1])) cur = intervals[0] for next in intervals[1:]: if next[0] > cur[1]: res.append(cur) cur = next else: # 当前区间进行扩大 cur[1] = max(cur[1], next[1]) res.append(cur) return res