合并区间：排好序，能并就并
按左端排完，重叠只可能发生在当前这段和下一段之间。新左端 ≤ 当前右端就扩右端；否则当前这段封口，另开一段。
按左端升序排序。维护当前合并段 cur。新区间左端 ≤ cur 右端则重叠，cur 右端改成两者较大值；否则把 cur 写入结果并换成新区间。最后一段也要写入。时间 O(n log n)，空间 O(n)。
给你若干闭区间 [start, end]，把所有重叠的合并成不相交的区间，返回合并后的列表。重叠包含端点相切：[1,4] 和 [4,5] 要并成 [1,5]。
主例 [[1,3],[2,6],[8,10],[15,18]]。 [1,3] 和 [2,6] 交在 [2,3]，并成 [1,6]；后面两段彼此不相交。答案 [[1,6],[8,10],[15,18]]。
不排序就两两查重叠是平方，还要处理「并完又和更前面的粘上」。本文要回答：排序之后为什么只看相邻，以及右端什么时候扩、什么时候封口。
左端有序之后，重叠不会跳过中间段
乱序时，一个区间可能和不相邻的另一个相交，中间还夹着一段无关的。合并 A 和 C 之后，新区间又可能回头和 B 相交，得反复扫。缺的是一个顺序，让「还可能和当前这段粘上的区间」全部排在后面、而且是连续的。
按左端升序。当前合并段是 [L, R]。后面每个区间的左端都 ≥ L。若某个后面的区间左端 > R，它和当前段不相交；再后面的左端更大，更不可能和当前段相交。所以一旦出现左端越过 R，当前段可以封口，不必回头。主例已经按左端排好，演示第一帧就是这个起点。
排序把任意变成相邻区间题先按一端排序，不是套路，是为了让「还可能重叠的」只剩下一段。不排就无法线性扫完。
左端还在当前右端里就扩，越过去就提交
cur 先等于第一段。扫后面每一段 [l, r]。l ≤ cur 的右端：两段有交集或相切，并成一段，左端仍是 cur 的左端（它更小，因为已按左端排序），右端取 max(cur 右端, r)——新段可能把右端推得更远，也可能被完全包住。l > cur 的右端：中间有空隙，cur 封口写入结果，cur 换成 [l, r]。扫完把最后的 cur 也写入。
用手走主例。cur=[1,3]。[2,6]：2≤3，右端扩成 6，cur=[1,6]。演示第一帧。 [8,10]：8>6，提交 [1,6]，cur=[8,10]。演示第二帧。 [15,18]：15>10，提交 [8,10]，cur=[15,18]，最后再提交。结果 [[1,6],[8,10],[15,18]]。
被包含的区间只并入、不新开。[1,10] 后面跟 [2,3]，2≤10 且 3<10，右端不变。相切要并：[1,4] 和 [4,5] 的 4≤4，必须扩成 [1,5]；写成 l < 右端会漏。只有一段时排序后直接返回它。
Go：排序 + 线性合并
func merge(intervals [][]int) [][]int {sort.Slice(intervals, func(i, j int) bool {return intervals[i][0] < intervals[j][0]})res := [][]int{intervals[0]}for _, it := range intervals[1:] {last := res[len(res)-1]if it[0] <= last[1] {if it[1] > last[1] { last[1] = it[1] }} else {res = append(res, it)}}return res}
1按左端排序。主例本来就有序，这一步仍不能省。
2结果里最后一段就是当前 cur。重叠只改它的右端。
3it[0] <= last[1] 含相切。右端只在更大时才写。
4否则另开一段。最后一段已经在 res 里，不用再补一次。
总结
按左端排序后，能并就扩右端，不能并就封口另开。主例并成 [1,6]，后面两段原样。
- 左端越过当前右端，再后面的更不可能粘上，可以封口。
- 相切要并，判断是 ≤ 不是 <。
- 被包含的段右端不必动。排序是 O(n log n) 的来源。