合并区间
Merge Intervals
合并所有重叠的区间，返回互不重叠且覆盖原范围的区间列表。
在力扣中练习题目描述
以数组 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] 可被视为重叠区间。
示例 3：
输入：intervals = [[4,7],[1,4]] 输出：[[1,7]] 解释：区间 [1,4] 和 [4,7] 可被视为重叠区间。
提示：
1 <= intervals.length <= 104intervals[i].length == 20 <= starti <= endi <= 104
解题思路
主解法
排序 + 一次扫描
按起点排序后，只需要和结果末尾比较
两个区间是否重叠，取决于起点和终点。如果直接两两比较，顺序是乱的，很难判断谁该和谁合并。
先按起点排序。排序后，可能重叠的区间一定相邻；扫描时只需要维护结果里的最后一个区间：
- 新区间起点大于最后区间的终点：不相交，直接加入结果；
- 否则相交：把最后区间的终点更新为两者的较大值。
自拟主例 [[2,4],[5,6],[1,3],[8,10],[7,9]] 排序后是 [1,3],[2,4],[5,6],[7,9],[8,10]；[2,4] 与 [1,3] 合并成 [1,4]，[8,10] 与 [7,9] 合并成 [7,10]。
分步图解
先按起点排序；之后只需要和结果里的最后一个区间比较。
- 区间数
- 5
分步图解
[7,9] 与上一个结果不相交，作为新区间加入。
- 结果数
- 3
时间 O(n log n)（排序），扫描 O(n)，空间 O(n)（结果）。
时间 O(n log n)空间 O(n)
易错点
- 只和前一个输入区间比较：前一个可能已经被合并进更早的区间，应该和结果末尾比较。
- 用 < 而不是 <= 判断相交：端点相接（如 [1,2] 和 [2,3]）也应合并。
- 合并时忘记取 max：新区间完全包含旧区间时，终点会被改小。
- 没有按起点排序：只按终点或原顺序扫描会漏掉跨区间的重叠。
代码与演示
演示输入
intervals = [[2,4],[5,6],[1,3],[8,10],[7,9]]先按起点排序；之后只需要和结果里的最后一个区间比较。
- 区间数
- 5
查看 C++ 代码
延伸阅读
- 区间题的通用第一步是排序：按起点排序适合合并，按终点排序适合安排最多不重叠区间。
- 插入区间（57）可以先找到插入位置，再复用“与末尾比较并扩展”的逻辑。