题目描述
给若干区间 [start, end]，把所有有重叠的合并掉，返回合并后互不重叠的区间列表。
思路解析
区间顺序乱时两两比，不光 O(n²) 慢，还容易漏掉「A 和 B 合并后，合出来的大区间又跟 C 重叠」这种连环情况，逻辑很绕。
转折：排序后，能重叠的区间必然相邻。证明很直观——若 A 起点 ≤ B 起点、A 和 C 重叠，那起点夹在中间的 B 一定也跟 A 沾边。于是只需从左到右扫一遍，拿当前区间跟「结果里最后一段 merged」比就够了：当前起点 ≤ merged 的终点就合并（终点取更大的），否则新开一段。一遍 O(n) 搞定，再不用两两回头比。
已按起点排序：本例输入起点恰好递增，排序后顺序不变：1、2、8、15。结果列表 merged 现在是空的。
处理 [1,3]：第一个 [1,3] 没东西可比，直接放进结果。当前合并段 [s,e] = [1,3]。
处理 [2,6] · 判重叠：[2,6] 的起点 2 没超过末段 [1,3] 的终点 3 → 重叠。该合并，而不是新开。
处理 [2,6] · 合并：合并时终点取更大的：max(3, 6)=6，末段被拉长成 [1,6]。注意起点 1 不变，只把终点往右拉。
处理 [8,10] · 负例：负例分支来了：[8,10] 的起点 8 已经超过末段 [1,6] 的终点 6，接不上 → 不合并，把 [8,10] 当新的一段 append 进结果。
[8,10] 新开后：现在结果末段换成了 [8,10]，接下来的区间只需要跟它比。前面合好的 [1,6] 已经定型，不再回头看。
处理 [15,18] · 判重叠：轮到最后一个 [15,18]。还是老规矩：拿它的起点 15，跟结果末段 [8,10] 的终点 10 比一比。
处理 [15,18] · 负例：[15,18] 的起点 15 又超过末段 [8,10] 的终点 10，同样接不上，再新开一段。扫完，结果 = [[1,6],[8,10],[15,18]]，三段互不重叠。
区间题的万能第一步——按端点排序。排完之后，绝大多数区间问题都能一遍扫描搞定，每个新区间只跟「结果里最后一段」打交道。
参考代码（Python）
1def merge(intervals):
2 intervals.sort(key=lambda x: x[0]) # 关键：先按起点排序
3 merged = []
4 for s, e in intervals:
5 if merged and s <= merged[-1][1]: # 和末段重叠
6 merged[-1][1] = max(merged[-1][1], e) # 合并：终点取 max
7 else:
8 merged.append([s, e]) # 接不上，新开一段
9 return merged复杂度分析
- 时间复杂度：O(n log n) —— 排序是 O(n log n) 主导；后面只扫一遍是 O(n)
- 空间复杂度：O(n) —— merged 结果列表最坏存下全部 n 个区间
套路模板
骨架记牢：排序 → 扫描 → 比末段终点决定合并还是新开。合并时终点一定取 max，别忘了。
1intervals.sort(key=lambda x: x[0])
2merged = []
3for s, e in intervals:
4 if merged and s <= merged[-1][1]:
5 merged[-1][1] = max(merged[-1][1], e)
6 else:
7 merged.append([s, e])易错点
- 错误写法：不排序直接扫 → 正确写法：先 intervals.sort(key=lambda x: x[0])（不排序时重叠区间未必相邻，一遍扫描会漏合并，比如 [[1,4],[5,6],[2,3]] 不排序就合不上 [1,4] 和 [2,3]）
- 错误写法：合并时直接 merged[-1][1] = e → 正确写法：merged[-1][1] = max(merged[-1][1], e)（当前区间可能被末段完全包住（e 更小），不取 max 会把终点改短，丢掉范围）
- 错误写法：判重叠用 s < merged[-1][1]（漏等号） → 正确写法：s <= merged[-1][1]（[1,3] 和 [3,5] 端点相接也算重叠，漏等号会错拆成两段）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。