题目描述
给若干区间 [start, end]，把所有有重叠的合并掉，返回合并后互不重叠的区间列表。
输入 = [[1,3],[2,6],[8,10],[15,18]]
输出 = [[1,6],[8,10],[15,18]]
思路解析
区间顺序乱的时候两两比，不光慢，还容易漏掉「合并后又跟别人重叠」的情况，逻辑很绕。
排序后，可能重叠的区间必然相邻。这样只需从左到右扫一遍，拿当前区间跟「结果里最后一个」比就够了。
判重叠只看一句：当前区间的起点，是不是没超过结果里最后那个区间的终点。是就合并（终点取更大的），不是就新开一段。
排序后，处理 [1,3]：已经按起点排好序。第一个 [1,3] 没东西可比，直接放进结果。
处理 [2,6]：[2,6] 的起点 2 没超过上一个的终点 3，重叠！合并成 [1,6]，终点取两者里更大的 6。
处理 [8,10]：[8,10] 的起点 8 已经超过上一段终点 6，接不上了，新开一个区间。
处理 [15,18]：[15,18] 同样接不上，再新开一段。扫完，结果就是 [[1,6],[8,10],[15,18]]。
区间题的万能第一步——按端点排序。排完之后，绝大多数区间问题都能一遍扫描搞定，只跟「结果里最后一个」打交道。
参考代码（Python）
Python
1def merge(intervals):
2 intervals.sort(key=lambda x: x[0]) # 关键：按起点排序
3 res = []
4 for s, e in intervals:
5 if res and s <= res[-1][1]: # 和上一段重叠
6 res[-1][1] = max(res[-1][1], e) # 合并：拉长终点
7 else:
8 res.append([s, e]) # 接不上，新开
9 return res复杂度分析
- 时间复杂度：O(n log n) —— 排序主导，扫描只 O(n)
- 空间复杂度：O(n) —— 存结果
套路模板
骨架记牢：排序 → 扫描 → 比末段终点决定合并还是新开。合并时终点一定要取 max，别忘了。
Python
1intervals.sort(key=lambda x: x[0])
2res = []
3for s, e in intervals:
4 if res and s <= res[-1][1]:
5 res[-1][1] = max(res[-1][1], e)
6 else:
7 res.append([s, e])易错点
- ❌ 不排序直接扫 → ✅ 先按起点 sort（不排序的话重叠区间未必相邻，一遍扫描会漏合并）
- ❌ 合并时直接用 e 当新终点 → ✅ res[-1][1] = max(res[-1][1], e)（当前区间可能被上一段完全包住（e 更小），不取 max 会把终点改短）
- ❌ 判重叠用 s < res[-1][1]（漏等号） → ✅ s <= res[-1][1]（[1,3] 和 [3,5] 端点相接也算重叠，要带等号）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。