合并区间

区间顺序乱时两两比，不光 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]]，三段互不重叠。

区间题的万能第一步——按端点排序。排完之后，绝大多数区间问题都能一遍扫描搞定，每个新区间只跟「结果里最后一段」打交道。

迁移阶梯：把这题练到能复述后，再去同类题里迁移：先复用状态定义，再调整边界条件。

边界三连：边界三连：极端输入先过一遍。

几个高频追问，记住答法。