1. 区间合并到底在解决什么问题
1.1 一堆时间轴糊在一起，就是区间的日常
先把话说白：区间合并（Merge Intervals）这件事，本质上是把一堆互相重叠、互相包含、互相挨着的"范围"揉成尽量少的几个大范围。输入是若干对数字[l, r]，输出是一组互不重叠、按顺序排好的区间，并且要求覆盖的范围和原来一模一样——一个点不能多，一个点也不能少。
我第一次接触这玩意儿是在排会议室的场景里：手上有一张表，几十个部门分别报了"我们想用 9:30 到 11:00""我们想用 10:00 到 12:00"，你作为行政要回答一个非常朴素的问题——"今天这间会议室到底有几个不可打断的占用大段？"如果答案是 3 段，那就能塞进去两段空闲时间做设备巡检；如果答案是 8 段，那今天别想干别的了。这就是最典型的区间合并需求。
它看起来简单到不像一道"算法题"，但恰恰是这种看着简单的题，在面试和工程里翻车率极高。因为坑都藏在边界上：左端点相等怎么办、右端点相等算不算重叠、[1,2]和[2,3]到底该不该并、坐标到了 10 的 9 次方会不会溢出、输入是闭区间还是半开区间。这些东西题目里往往一句话带过，但写错一个符号就是全错。
1.2 四个真实场景，说明它不只是刷题
很多人觉得区间合并是"LeetCode 专属玩具"，其实它趴在很多工程的角落里。
日程与资源排布。会议室、工位、充电桩、客服坐席，凡是"同一时刻只能被一个任务占用"的资源，都要先把碎片化的预约合并成连续占用段，再据此计算空闲窗口。空闲窗口的计算其实就是"合并结果的补集"，这一步后面会专门讲。
内存与磁盘分配。内存分配器维护一张空闲块表，释放内存时会产生大量相邻的空闲块，如果不合并，就会碎片化到再也分配不出大块。这一块的实现方式和我们写的区间合并几乎是同一个骨架，只不过它们用的是平衡树或者空闲链表而不是数组排序。
网络地址段与权限范围。访问控制列表里经常出现多条互相包含的地址段，比如10.1.0.0/16和10.1.2.0/24，前者已经把后者吞掉了。规则匹配前先做一次合并，既能减少规则条目，也能避免"规则顺序不同导致结果不同"这种诡异 bug。
数据清洗与统计口径。埋点日志里同一次会话被切成了很多段，统计会话时长时要把间隔小于 30 秒的段并起来；基因组学里合并测序得到的区间；剪辑时间轴上去掉冻结帧后合并剩余片段。这些都是同一个套路。
1.3 合并到底"合"的是什么：三种重叠形态
判断两个区间能不能合并，只看一件事：它们的交集是否非空（或者按题目要求，是否"相邻即算连续"）。具体有三种形态：
| 形态 | 示例 | 合并结果 | 说明 |
|---|---|---|---|
| 部分重叠 | [1,4]、[3,7] | [1,7] | 最常见，左右端点各取极值 |
| 完全包含 | [1,10]、[3,5] | [1,10] | 必须用max保住大右端点，这里最容易翻车 |
| 端点相接 | [1,2]、[2,3] | 看题目口径 | 闭区间通常算连续可并；半开区间则本来就不重叠 |
第三种形态是分水岭。如果题目说区间是实数的闭区间[l, r]，那[1,2]和[2,3]在点 2 处共享一个点，可以合并；如果题目规定是半开区间[l, r)，那[1,2)和[2,3)完全不相交，强行合并就错了。所以拿到题目第一件事，是确认区间口径，而不是急着敲代码。
提示：判断条件写成
l <= curR还是l < curR，唯一依据就是区间口径。这个符号选错，样例可能还过，一交就 WA 一半。
2. 核心思路拆解：排序加一次扫描
2.1 为什么必须先排序：无序扫描会漏
假设不排序，直接两两比较能不能并？思路是有的——拿第一个区间去和后面所有区间比，能并就并，并完再回头重新扫一遍，直到某一轮没有任何合并发生。这个做法能出正确答案，但复杂度是 O(n²) 甚至 O(n³)，几千个区间就卡住了。
排序的价值在于把"两两比较"降维成"只看相邻"。只要把所有区间按左端点从左到右排好，那么任意两个可能重叠的区间，在排序后的序列里一定是挨着出现（或者在更早的位置就已经并掉了）。于是你只需要维护"当前正在生长的这个合并区间"，从左往右滑一遍，每一步只做一次判断。这就是排序带来的全部收益，也是它能从 O(n²) 降到 O(n log n) 的根本原因。
排序键选左端点就够了，不需要同时排右端点。理由很直白：左端点决定了谁先被处理，而右端点的大小在处理过程中会用max动态修正。排右端点除了浪费比较开销，还会破坏左端点的自然顺序，反而添乱。
2.2 贪心扫描的不变量，用一句话说清
扫描过程中始终维护两个变量：curL和curR，代表"目前已经吃完的这一坨的最终左端点和已知最大右端点"。这个不变量的含义是：
[curL, curR]是当前这一坨从最左端出发能覆盖到的完整范围，左边不可能再有东西了，右边还可能有待扩展。
对每个新区间[l, r]，只有两种命运：
- 断开：
l > curR，说明它和当前这一坨中间真的有空隙，没有任何点重叠。此时把[curL, curR]结算进结果数组，然后让curL = l、curR = r，开启新的一坨。 - 粘连：
l <= curR，说明有交集或者直接接上了。此时curL一定不需要改（因为排序保证l >= curL），只需要curR = max(curR, r)。那个max就是用来对付"完全包含"这种形态的——[1,10]后面跟一个[3,5]，如果你写成curR = r，答案立刻变成[1,5]，范围凭空少了一大截。
最后一步是几乎所有手写实现都会忘的：循环结束后，最后一坨[curL, curR]还没有被结算进结果数组，必须手动补上。这个 bug 的典型症状是"输入一个区间时输出空数组"或者"输入全部重叠时只少了一段"。
2.3 边界相等算不算重叠：一个符号定生死
我见过最多的翻车点就在这个符号上。把两种常见口径列清楚：
整数闭区间[l, r]，即包含所有整数点。此时[1,2]和[2,3]共享整数点 2，应当合并。判断条件写l > curR才算断开，等价于l <= curR合并。
实数闭区间[l, r]，即包含中间所有实数。同样在点 2 处相交，处理方式和上面一致。
半开区间[l, r)。[1,2)和[2,3)没有公共点，不能合并。判断条件要改成l >= curR才算断开，即l < curR才合并。
还有一种更刁钻的变体是"相邻即算连续"，比如题目说"间隔小于等于 0 的段合并"（这是标准重叠），而有些业务说"间隔小于等于 5 分钟的段合并"。后者其实是在原区间上做了膨胀：把每个右端点加 5 再合并，然后再把右端点减回去。这招我用过好几次，比在扫描逻辑里塞一个阈值分支干净得多。
2.4 复杂度、数据结构与不变量校验
时间复杂度由排序主导，O(n log n)；扫描本身是O(n)。空间复杂度取决于实现：如果新建结果数组，是O(n)；如果允许原地覆盖输入数组（像 LeetCode 上那样把输入当草稿纸），可以做到O(1)额外空间。
数据结构的选择取决于使用模式：
- 一次性批处理：数组加排序，最简单也最快，缓存友好。
- 持续动态插入/删除：用有序映射（C++ 的
std::map、Java 的TreeMap、Python 的sortedcontainers.SortedList），每次插入后在前后邻域做局部合并，单次操作O(log n)。 - 高频查询最大重叠深度：扫描线加差分数组，或者线段树维护区间加与全局最大值。
我自己写业务代码时的默认选择是数组排序。除非插入频率明显高于查询频率，否则有序容器的常数因子和内存开销都不划算。
心得：写完后一定要在心里跑三个样例——全部分离、全部重叠、单区间。这三个能扛住，绝大多数边界就稳了。
3. 手把手写参考代码（四种语言）
3.1 C++ 版本：从暴力到 O(n log n)
先给一个最容易理解但会超时的暴力版本，目的是让你看清"排序到底省了什么"：
// 暴力版：反复扫描，直到一轮没有合并发生 vector<vector<int>> mergeBrute(vector<vector<int>> a) { bool changed = true; while (changed) { changed = false; for (size_t i = 0; i < a.size() && !changed; ++i) for (size_t j = i + 1; j < a.size(); ++j) { if (a[i][0] <= a[j][1] && a[j][0] <= a[i][1]) { a[i][0] = min(a[i][0], a[j][0]); a[i][1] = max(a[i][1], a[j][1]); a.erase(a.begin() + j); changed = true; break; } } } sort(a.begin(), a.end()); return a; }正解版本把上面的循环彻底删掉，只留一趟扫描：
vector<vector<int>> merge(vector<vector<int>>& intervals) { if (intervals.empty()) return {}; sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) { return a[0] < b[0]; // 只按左端点，右端点不参与 }); vector<vector<int>> res; int curL = intervals[0][0], curR = intervals[0][1]; for (size_t i = 1; i < intervals.size(); ++i) { int l = intervals[i][0], r = intervals[i][1]; if (l > curR) { // 严格大于才断开 res.push_back({curL, curR}); curL = l; curR = r; } else { curR = max(curR, r); // 这里必须取 max } } res.push_back({curL, curR}); // 补上最后一坨 return res; }三个细节值得单独说。第一，比较器里绝对不要写a[0] <= b[0]，std::sort要求严格弱序，用<=在某些实现下会直接越界崩溃，这个坑我在早期踩过一次，调试了半天才发现是比较器的锅。第二，res.push_back({curL, curR})里用花括号初始化，比先造一个临时vector再 push 少一次拷贝。第三，如果题目允许修改输入，可以把结果直接写回intervals[write++]，把额外空间压到O(1)。
3.2 Python 版本：简洁写法与性能陷阱
Python 写起来最短，但有几个陷阱：
def merge(intervals): if not intervals: return [] intervals.sort(key=lambda x: x[0]) res = [] cur_l, cur_r = intervals[0] for l, r in intervals[1:]: if l > cur_r: res.append([cur_l, cur_r]) cur_l, cur_r = l, r elif r > cur_r: cur_r = r res.append([cur_l, cur_r]) return res第一个陷阱是排序方式。intervals.sort()不加key会按元组的字典序排，也就是左端点相同时右端点也参与比较。这在纯合并题里不影响结果，但在"删除被覆盖区间"那类题里会直接改变答案，因为那道题需要左端点相同的区间按右端点降序排。养成显式写key的习惯，能避免大量隐性错误。
第二个陷阱是intervals[1:]这个切片。它复制了一份列表，区间数量到百万级时会明显吃内存。写成索引循环for i in range(1, len(intervals))就没这个问题，代价是代码长一点。
第三个陷阱是元组解包的误用。cur_l, cur_r = intervals[0]要求每个元素恰好两个值，如果输入偶尔混进了长度不对的列表，会抛ValueError。做数据清洗的时候，我一般会在前面加一道校验，把长度不为 2 的条目先剔出去，比在循环里做 try 干净。
3.3 Java 与 Go：比较器和切片的两点差异
Java 的坑集中在排序。int[][]不能用Arrays.sort(intervals)直接按第一列排（那样是按行字典序），必须传比较器。而且比较器里要用Integer.compare(a[0], b[0])而不是a[0] - b[0]，因为相减在极端值下会溢出，导致排序结果错乱——这个 bug 特别隐蔽，只有坐标接近Integer.MIN_VALUE或MAX_VALUE时才暴露。
public int[][] merge(int[][] intervals) { if (intervals == null || intervals.length == 0) return new int[0][]; Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0])); List<int[]> res = new ArrayList<>(); int curL = intervals[0][0], curR = intervals[0][1]; for (int i = 1; i < intervals.length; i++) { if (intervals[i][0] > curR) { res.add(new int[]{curL, curR}); curL = intervals[i][0]; curR = intervals[i][1]; } else { curR = Math.max(curR, intervals[i][1]); } } res.add(new int[]{curL, curR}); return res.toArray(new int[res.size()][]); }Go 这边sort.Slice用闭包，逻辑很直观，但要注意append的扩容语义：如果结果切片是从已有的切片派生出来的（比如res := intervals[:0]），后续 append 会覆盖原数组内容。做原地合并时这是优点，做纯函数时就是隐患，得用make单独分配。
func merge(intervals [][]int) [][]int { if len(intervals) == 0 { return [][]int{} } sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] }) res := make([][]int, 0, len(intervals)) curL, curR := intervals[0][0], intervals[0][1] for i := 1; i < len(intervals); i++ { l, r := intervals[i][0], intervals[i][1] if l > curR { res = append(res, []int{curL, curR}) curL, curR = l, r } else if r > curR { curR = r } } return append(res, []int{curL, curR}) }3.4 用测试用例自检：边界样例清单
写完代码别急着提交，先把下面这组用例过一遍。我把它们按"能杀死哪类 bug"归类：
| 用例 | 期望输出 | 专门用来抓什么 |
|---|---|---|
[] | [] | 空输入未处理 |
[[1,4]] | [[1,4]] | 忘记补最后一坨 |
[[1,4],[4,5]] | [[1,5]] | 端点相接的判断符号 |
[[1,10],[2,3]] | [[1,10]] | 忘记取max |
[[1,2],[3,4]] | 原样 | 无重叠时误合并 |
[[5,6],[1,2],[3,4]] | 三个独立区间 | 排序缺失或排序键错误 |
[[1,4],[0,4]] | [[0,4]] | 左端点被覆盖时curL的处理 |
其中[[1,4],[0,4]]这条特别值得一提。合并后左端点应该是 0 而不是 1。因为我们按左端点排序，[0,4]会排在前面，所以标准算法里curL天然是 0，不需要额外取 min。但如果你用了原地去重的写法，或者在动态插入场景里没排序，就很容易忘记更新左端点。这也是我建议"批处理一律先排序"的另一个理由：排序帮你把curL的更新问题消掉了。
4. 六个高频变体与例题思路分析
4.1 变体一：插入区间，三段式最稳
插入区间（LeetCode 57）是合并的直接扩展：给一个已排好序且互不重叠的区间列表，再插入一个新区间，要求保持有序不重叠。标准解法是把整个过程切成三段：
- 左边干净段：所有右端点小于新区间左端点的区间，它们和新区间完全无关，原样输出。
- 中间合并段：所有左端点小于等于新区间右端点的区间，它们和新区间有交集，不断把新区间左右端点扩张。
- 右边干净段：剩下的全部原样输出。
vector<vector<int>> insert(vector<vector<int>>& a, vector<int>& t) { vector<vector<int>> res; int i = 0, n = a.size(); while (i < n && a[i][1] < t[0]) res.push_back(a[i++]); // 左边 while (i < n && a[i][0] <= t[1]) { // 中间 t[0] = min(t[0], a[i][0]); t[1] = max(t[1], a[i][1]); ++i; } res.push_back(t); while (i < n) res.push_back(a[i++]); // 右边 return res; }为什么不用"插入再整体合并"？因为那样是O(n log n)，而三段式利用了输入本身有序的特性，做到O(n)。数据量大时差距明显。
4.2 变体二：无重叠区间与最少箭数，换个排序键
无重叠区间（LeetCode 435）问的是"最少删掉几个区间，让剩下的互不重叠"。最少删 = 总数 − 最多能留下几个不重叠的。这里的关键是：贪心要按右端点排序，而不是左端点。每次选右端点最小的、且和上一个选择不冲突的区间，这样给后面留的空间最大。
最少箭数（LeetCode 452）的骨架几乎一模一样：一支箭能穿过一组互相重叠的区间，问最少几支箭。答案就是最大不重叠区间数——注意这里的判断条件是start > lastEnd才需要新箭，因为[1,2]和[2,3]可以被同一支箭在点 2 处穿过，和闭区间的合并口径保持一致。
这两个题放在一起讲，是因为它们共享同一个思维：按右端点排序 + 贪心选择。什么时候用左端点排序，什么时候用右端点排序？我的判断标准是：问题要求"输出合并后的区间列表"，用左端点；问题要求"最大化留下的数量/最小化资源数"，用右端点。
4.3 变体三：合并总长度与最大重叠深度，扫描线上场
有时候不需要具体区间，只要一个数。比如"所有区间合并后的总长度"和"同时存在的最大区间数量"。
总长度可以在合并过程中直接累加：每结算一坨，就把curR - curL加进答案（整数闭区间的长度是curR - curL + 1，实数区间是curR - curL，别搞混）。
最大重叠深度用扫描线更合适。把每个区间拆成两个事件：左端点+1，右端点-1，排序后扫一遍，累加过程中出现的最大值就是深度。闭区间和半开区间在这里的差别体现在同坐标事件的先后顺序上：
def max_overlap(intervals): events = [] for l, r in intervals: events.append((l, 1)) events.append((r, -1)) # 闭区间：同一坐标先处理 +1，让相接的两个区间也算重叠 events.sort(key=lambda e: (e[0], -e[1])) cur = best = 0 for _, delta in events: cur += delta best = max(best, cur) return best半开区间的写法只要把排序键改成(e[0], e[1])——同一坐标先处理-1，让[1,2)结束后[2,3)才开始。这个顺序差别看起来只有一行，却是扫描线题最常见的失分点。
4.4 变体四：区间交集与区间列表交集
单对区间求交集很直接：lo = max(l1, l2)、hi = min(r1, r2)，lo <= hi则有交集。但"两个区间列表的交集"（LeetCode 986）就有意思了，因为两个列表各自的区间都是有序不重叠的，可以用双指针线性扫。
思路是：每次比较两个当前区间，先算出交集放进结果，然后把右端点较小的那个指针往前推。这一步的道理是，右端点小的那个区间已经不可能再和后面任何区间产生交集的"新内容"了，因为后面所有区间的右端点都更大。这个腾挪逻辑和归并排序的 merge 步骤神似。
vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) { vector<vector<int>> res; int i = 0, j = 0; while (i < A.size() && j < B.size()) { int lo = max(A[i][0], B[j][0]); int hi = min(A[i][1], B[j][1]); if (lo <= hi) res.push_back({lo, hi}); if (A[i][1] < B[j][1]) ++i; else ++j; } return res; }4.5 变体五：区间补集与区间删除
补集就是"合并结果的反面"，计算空闲窗口、可预约时段都要用。做法是：先合并，再从域的左端点开始，把合并结果之间的缝隙抠出来。
def complement(intervals, domain_l, domain_r): merged = merge(intervals) res = [] cur = domain_l for l, r in merged: if l > cur: res.append([cur, l - 1]) # 整数闭区间，缝隙到 l-1 cur = max(cur, r + 1) if cur <= domain_r: res.append([cur, domain_r]) return res两个坑。第一，l - 1和r + 1只适用于整数闭区间，如果是实数区间，缝隙就是[cur, l]，不需要加减一。第二，merged里可能出现在域外的大区间，所以cur = max(cur, r + 1)里的max不能省，否则cur会被一个更小的r + 1拽回去，产生错误的重复缝隙。
区间删除是补集的对偶操作：把要删的区间补齐，然后和大区间求交、取差。批量删除时，先合并所有删除项，性能会好不少。
4.6 变体六：删除被覆盖区间与划分字母区间
删除被覆盖区间（LeetCode 1288）有个漂亮的排序技巧：左端点升序，右端点降序。为什么？因为左端点相同的区间里，右端点最大的那个一定覆盖其他所有同左端点的区间。排完之后从左往右扫，维护已见的maxR，只要当前右端点> maxR就说明它没被覆盖，计数加一；否则就是被覆盖，跳过。
int removeCoveredIntervals(vector<vector<int>>& a) { sort(a.begin(), a.end(), [](const vector<int>& x, const vector<int>& y) { if (x[0] != y[0]) return x[0] < y[0]; return x[1] > y[1]; // 同左端点，右端点降序 }); int cnt = 0, maxR = -1; for (auto& iv : a) { if (iv[1] > maxR) { ++cnt; maxR = iv[1]; } } return cnt; }划分字母区间（LeetCode 763）看起来毫不相干，其实是"每个字母的首次出现到末次出现构成一个区间"，然后对这些区间做合并，合并后有几坨就分几段。这就是我特别喜欢这道题的原因——它把"构造区间"和"合并区间"两个步骤串起来了，非常适合作为检验理解的综合练习。
5. 常见错误与排查技巧实录
5.1 排序比较函数的三个暗雷
比较器看着最不起眼，出问题却最难查，因为错误往往是"偶尔错一次"。
暗雷一：非严格弱序。写return a[0] <= b[0]，当两个区间左端点相同时比较器返回 true，而反过来的比较也返回 true，破坏了"相等元素互不大于"的约定。std::sort在数据量大时会走内省排序，一旦触发就可能在数组边界外乱跳，表现为随机崩溃或者结果错乱。修法就是老老实实用<。
暗雷二：相减溢出。return a[0] - b[0];在坐标接近整型极值时结果溢出，符号翻转，排序结果完全错。用Integer.compare或显式的比较分支。
暗雷三：排序键不完整。1288 那道题如果只按左端点排，同左端点的顺序不确定，导致maxR的判断随机出错。凡是题目对"同键元素"有额外要求，排序键里必须显式带上第二个维度。
心得：写完比较器，心里默念一遍"如果两个元素完全相同，它返回什么"。答案必须是 false。
5.2 最后一个区间被吃掉：一个高频低级错误
这个 bug 的形态极其固定：循环里只处理了[0, n-2]到[1, n-1]的转移，最后一坨忘了push。测试用例用单个区间，结果是空数组；用全部重叠的区间，结果少一段。修法也简单，循环结束后补一行。
但还有更隐蔽的变体。如果你用的是"当发现断开时结算"的写法，那么最后一坨永远不会触发"断开"分支，所以必须手动补。如果你用的是"每轮先扩张再结算"的写法，就要检查结算是否重复。我自己的习惯是固定用第一种写法，因为逻辑最好验证。
5.3 原地修改与引用共享的隐蔽 bug
为了压空间，很多人会原地把合并结果写回输入数组。这本身没问题，但要小心两件事。一是在写回之前不能再用旧数据，比如你一边读intervals[i]一边往intervals[write]写，而write <= i恒成立，所以读的位置永远在写的位置之后，是安全的；但如果你的循环顺序是倒着来的，就完蛋了。二是调用方可能还在用这个数组，Python 和 Go 里的切片/引用共享语义会让"被调用函数悄悄改了入参"，这种 bug 在跨模块调用时很难定位。
我的做法是：除非题面或性能明确要求原地，一律返回新数组。可读性和安全性远比那点内存值钱。
5.4 数据类型、溢出与精度
坐标范围到 10 的 9 次方、数量到 10 的 5 次方时，长度累加可能突破 32 位整数上限。求总长度、求面积覆盖这类题，累加变量一定要用 64 位整型。C++ 用long long，Java 用long，Go 用int64，Python 天然任意精度不用管，但要注意它慢。
浮点坐标是另一个雷区。用double判断区间是否重叠，端点相等时容易因为精度问题判错。稳妥做法是把浮点坐标放大成整数（比如时间精确到毫秒就乘 1000 转成整数），全程用整数运算，需要输出时再除回去。
5.5 排查速查表
| 症状 | 最可能的原因 | 快速验证方法 |
|---|---|---|
| 单区间输入返回空 | 漏补最后一坨 | 用[[1,4]]跑 |
| 包含关系的结果变短 | 忘了curR = max(curR, r) | 用[[1,10],[2,3]]跑 |
| 端点相接的没合并 | 判断条件用了>= | 用[[1,4],[4,5]]跑 |
| 结果顺序乱 | 排序键写错或没排序 | 检查比较器 |
| 大规模随机崩溃 | 比较器非严格弱序 | 加assert或换< |
| 长度累加为负数 | 32 位整型溢出 | 换 64 位整型 |
| 最大深度偶尔少 1 | 扫描线同坐标事件顺序反了 | 检查排序键的第二项 |
6. 工程化落地与性能调优
6.1 流式与超大规模区间怎么处理
数据量大到内存放不下时，数组排序就行不通了。可行的路子有三条。
外部排序。把区间按左端点分成若干块，每块内部排好序写临时文件，然后做 k 路归并，归并的同时做合并，一次只持有 k 个区间在内存里。这套做法和数据库的排序归并连接是一个思路。
分桶后局部合并。如果坐标范围已知且不算太大，可以按坐标分桶，每个桶内独立合并，再处理桶边界的粘连。坐标范围到 10 的 9 次方就不适用了，适合坐标比较密集的场景。
预合并 + 有序结构。如果数据是分批到达的，可以维护一个有序容器，每次插入后在邻居附近做局部合并。Python 里没有内置的有序容器，bisect加列表的插入是O(n)，数据大时改用sortedcontainers或者干脆自己写跳表。
6.2 线段树、有序集合的取舍
需求一旦变成"动态增删区间 + 随时查询被覆盖的总长度"，单纯的合并就力不从心了。这时候要上带懒标记的线段树，支持区间赋值、区间加和全局求和。坐标范围大时先做离散化，把端点压缩到2n个刻度上，线段树的规模就降到可接受范围。
有序集合适合"插入区间时自动合并重叠邻居"的场景，典型实现是维护一个start -> end的映射，插入[l, r]时先找到所有左端点落在[l, r]范围内的条目，把它们和[l, r]一起并成一个大的，再删旧插新。这套逻辑在内存分配器和区间调度器里非常常见。
我的建议是：能排序解决的绝不上线段树。线段树的代码量和调试成本是排序版本的五到十倍，只有确实需要在线查询时才值得。
6.3 一份可复用的合并模板
最后给你一份我自己用了很久的 C++ 模板，把常见需求都做成可选项，改一个枚举就切换行为：
struct Interval { long long l, r; }; enum class Touch { Strict, Adjacent }; // 相接是否算连接 vector<Interval> mergeIntervals(vector<Interval> a, Touch mode = Touch::Adjacent) { if (a.empty()) return {}; sort(a.begin(), a.end(), [](const Interval& x, const Interval& y) { return x.l < y.l; }); vector<Interval> res; long long curL = a[0].l, curR = a[0].r; for (size_t i = 1; i < a.size(); ++i) { bool connected = (mode == Touch::Adjacent) ? (a[i].l <= curR) : (a[i].l < curR); if (!connected) { res.push_back({curL, curR}); curL = a[i].l; curR = a[i].r; } else { curR = max(curR, a[i].r); } } res.push_back({curL, curR}); return res; }把它包一层，还能顺手算出总长度、区间个数和最大深度：
struct MergeStat { vector<Interval> merged; long long totalLen; // 实数长度；整数长度请自行 +1 int segments; }; MergeStat analyze(vector<Interval> a, Touch mode = Touch::Adjacent) { auto m = mergeIntervals(std::move(a), mode); long long len = 0; for (auto& iv : m) len += iv.r - iv.l; return {m, len, (int)m.size()}; }这套封装上了生产环境之后，我发现最大的收益不是性能，而是口径统一：所有调用方都通过Touch明确表达自己的相接语义，再也不会出现"A 模块认为相接算连接、B 模块认为不算"导致统计口径对不上的问题。这类问题在多人协作的项目里比算法本身的 bug 更难查——因为每一段代码单独看都是对的。
最后分享一个我自己的小习惯：凡是要写合并逻辑的地方，先花两分钟用纸把测试用例画成数轴上的线段图，把端点的开闭、相接的处理、域外的过滤在图上标一遍。画完再动手，比写完再调省的时间多得多。区间合并这类题的难点从来不在代码长度，而在你脑子里那张图是否清晰。
