企业官网建设流程全解析

区间合并这四个字，乍一听像是某种数据处理里顺手就能写完的小工具，实际动手才发现它出现的频率高得离谱：算法面试里它是最经典的排序加贪心组合，工程代码里它被用来归并日志时间段、合并内存碎片、压缩日程冲突。它的核心任务说穿了只有一句话——给一堆可能互相重叠的区间，把重叠的部分揉成一块，最终得到一组互不相交、按位置排好的干净区间。可就是这么个东西，我前后在面试里被问过三四次，每次在白纸上重写都还是会先在边界条件上卡一下：两个区间端点刚好相接，算重叠吗？输入是空的怎么办？坐标大到开不下数组又怎么处理？这篇就把区间合并从头到尾拆开讲，思路推演、参考代码、典型例题、踩过的坑全部写清楚，不管你是刚开始接触还是已经写过几遍想回头复习细节，应该都能捞到点东西。

1. 先搞清楚区间合并到底在合并什么

1.1 一个看似朴素却容易想歪的需求

先给最直接的定义。所谓区间，就是一对数字 [l, r]，表示从 l 到 r 的这一整段，l 叫左端点，r 叫右端点。给你一个区间集合，比如 [[1,3], [2,6], [8,10], [15,18]]，其中 [1,3] 和 [2,6] 有重叠部分 [2,3]，所以它们应该被合并成 [1,6]；而 [8,10] 和 [15,18] 谁也不挨着谁，原样保留。最终输出 [[1,6], [8,10], [15,18]]，这就是区间合并的标准结果。

这里有个很容易被忽略的隐含要求：输出的区间之间不能有任何重叠，而且顺序必须是按左端点递增排好的。很多人第一次写的时候只想着"把重叠的合起来"，写完之后发现输出里 [8,10] 排在 [1,6] 前面，或者两个本该合并的区间因为顺序问题被漏掉了。所以区间合并的完整定义应该包含两条：合并所有有交集的区间，同时保证输出有序且互不相交。

再往下想一层，为什么"互不相交"这么重要？因为互不相交意味着这组区间可以直接用来做二分查找、可以直接做长度求和、可以直接当成一个稀疏的覆盖集合去查询某个点是否被覆盖。如果区间之间还有重叠，你算出来的总覆盖长度就会重复计数。这是区间合并最常见的下游用途——它不是终点，而是后续查询和统计的前置清洗步骤。

1.2 两个区间之间的关系只有三种

理解区间合并的关键，是先把两个区间之间所有可能的关系穷举清楚。给定区间 A = [a1, a2] 和 B = [b1, b2]，并且假设 a1 <= b1（也就是 A 的左端点不比 B 靠右），那么它们的关系其实只有三种：

这张表里最有价值的一列是"合并结果"：不管哪种相交情况，合并后的左端点都是 a1，右端点都是 max(a2, b2)。这就把三种关系里两种情况统一成了一个表达式。也就是说，只要判定 b1 <= a2，就说明两者有交集，新右边界取两者右端点的较大值。这个结论看起来平平无奇，但它正是后面整个算法的支点。

我特意把 a1 <= b1 这个前提写出来，因为它解释了一件事：为什么必须排序。如果不排序，你拿到两个区间得先判断谁在左边，才能套用上面这套判断；而一旦区间数量上去，两两判断的开销就是平方级别。排序的价值在于，它一次性把所有"谁在左边"的问题解决掉，让后面的判断可以只看相邻的两个。

1.3 无序输入带来的组合爆炸

有人会问，我能不能不排序，直接遍历每个区间，跟已有的结果集逐个比对，能合并就合并？技术上可以，但代价是 O(n²) 甚至更高，因为每合并一次，结果集里的区间可能又要跟别的区间合并，你需要反复迭代直到不再发生变化。

举个极端点的例子：给 10000 个区间，每个区间只跟前一个重叠一点点，首尾相接成一条长链。用暴力比对的方式，每一次插入新区间都要扫描整个结果集，总共就是大约 5000 万次比较；而排序加扫描只需要先花 O(n log n) 排个序，再线性扫一遍，总操作量在十几万这个量级。差了三个数量级，输入规模再大一点就是"能跑"和"跑不动"的区别。

所以区间合并的标准解法骨架就定下来了：先按左端点排序，再用一次线性扫描完成合并。排序把区间在数轴上从左到右整齐排好，扫描时只需要维护"当前正在拼装的这一块"的左右边界，遇到能接上的就往后延，接不上就把当前这块落盘，另起一块。整套流程的时间复杂度是 O(n log n)，空间复杂度在不考虑输出数组的情况下是 O(1)。

2. 把过程在纸上跑一遍：排序加扫描的完整推演

2.1 排序键为什么选左端点而不是右端点

先说排序这件事本身。最常见的写法是按左端点升序排，也就是[1,3]排在[2,6]前面。为什么不是按右端点？因为扫描过程中我们要判断的核心问题是"下一个区间能不能接上当前这一块"。当前这一块的右边界是已知的，我们关心的是下一个区间的左端点有没有越过它。左端点有序之后，我们只需要一路往后看，一旦某个区间的左端点超过了当前右边界，后面所有的区间左端点只会更大，就更不可能接上了。这个性质让"提前结束"成为可能，也是算法能够线性扫描的根本原因。

如果换成按右端点排序，判断逻辑就变得别扭：你看到右端点大的区间，并不知道它的左端点在哪里，可能它从很左边就开始，也可能只是在很右边的一小段。你可以把算法改成按右端点排的版本，但判断条件会绕好几道弯，可读性和出错率都不如前者。

还有一个细节：左端点相同时，右端点按什么顺序排？标准 C++ 里pair的默认比较是先比 first 再比 second，也就是左端点相同的时候右端点小的排前面。这会不会影响结果？不会。因为扫描时我们对右边界取的是max，无论小的先来还是大的先来，最终右边界都会取到大的那个。但有一个场景例外——如果题目要求你返回合并后的区间，并且期望右端点尽量大，那么排序顺序本身不影响正确性，只是会影响中间状态。所以左端点相同时右端点怎么排都可以，图省事就用默认比较。

2.2 扫描过程中被维护的那个状态

排序完成之后，扫描阶段只需要维护两个变量：curL和curR，表示"当前正在拼装的这块区间"的左右边界。整个循环的不变量（可以理解成每一步都保证为真的事实）是这样的：在处理第 i 个区间之前，[curL, curR] 已经完整包含了前面 i 个区间的全部内容，并且它是这 i 个区间能拼出的、包含 i-1 号区间的那一整块。

这个不变量听起来有点绕，换个说法就清楚了：每次拿一个新的区间进来，只需要问一句"你的左端点有没有越过我的右边界"。

• 如果没越过，说明两者有交集，新的右边界更新为max(curR, 新区间右端点)；
• 如果越过了，说明新的区间跟当前这块彻底断开，当前这块已经完整了，可以落盘，然后把curL、curR换成新区间的左右端点，开始拼新的一块。

循环结束后别忘了最后一块。这是新手最容易漏的一步——因为落盘动作是写在else分支里的，最后一块永远不会进入else，必须在循环外面补一次 push。我自己写这段代码时养成的习惯是：只要写了"在循环里落盘"的逻辑，循环外面必定配一句收尾，写的时候心里默念一遍，能省掉很多无谓的调试。

2.3 拿一组数据把每一步摊开看

用 [[1,3], [2,6], [8,10], [15,18]] 这组数据完整推一遍。排序后顺序不变，依次处理：

再看一组能体现"包含"关系的：[[1,10], [2,3], [4,5], [12,13]]。排序后是 [[1,10], [2,3], [4,5], [12,13]]：

注意第 1、2 步里 curR 完全没有变化，这说明被包含的区间在取 max 的时候会被自动吸收掉，不需要额外写"判断是否被包含"的分支。这一点在代码里体现为只用一句curR = max(curR, r)就搞定，逻辑非常紧凑。

2.4 端点相接到底算不算重叠

这是区间合并里最有争议的一个点，也是面试官最爱拿来追问的点：[1,3]和[3,5]能不能合并成[1,5]？

答案取决于区间的开闭性。如果区间是闭区间[l, r]，也就是包含两个端点，那么点 3 同时属于两个区间，它们是相交的，可以合并成[1,5]。如果区间是半开区间[l, r)，那么 3 属于前者但不属于后者，两者刚好"擦肩而过"，不重叠，自然不能合并。还有一种情况是开区间(1,3)和(3,5)，中间那个点 3 谁都不包含，也不能合并。

所以判断条件里的那个不等号，是<=还是<，完全由题目对区间开闭性的定义决定。现实里绝大多数题目默认闭区间，用<=；少数题目会明确说明"端点相接不算重叠"，那就换成<。我的建议是：写代码之前先把这两个字符确认清楚，并且在代码旁边写一句注释，因为读到这一段的人（包括三个月后的你自己）根本没法从<=反推出题目意图。

顺带说一个真实踩坑：我有一次做日志时间段合并，业务方给的时间段是[start, end)这种半开区间，结果我下意识按闭区间写了<=。本来两段日志在时间上严丝合缝地衔接（前一段的结束时间等于后一段的开始时间），按业务定义应该保持分开，结果被我合成了一大段，导致后续按段统计的时候少算了一次切换。小小一个符号，排查了快两个小时。

3. 参考代码逐行拆解：从伪代码到能过的实现

3.1 通用伪代码与三个必须记住的点

先用伪代码把结构固定下来，不管换什么语言，骨架都是这一套：

输入：区间列表 intervals 1. 如果 intervals 为空，直接返回空结果 2. 按左端点升序排序 3. curL, curR = intervals[0] 的左右端点 4. 对 i 从 1 到 n-1： if intervals[i].左端点 <= curR: curR = max(curR, intervals[i].右端点) else: 结果集加入 [curL, curR] curL, curR = intervals[i] 的左右端点 5. 结果集加入 [curL, curR] // 收尾 6. 返回结果集

三个容易出问题的点，我在伪代码里都标出来了。第一是第 1 步的空判断，如果没有它，第 3 步取intervals[0]就直接越界了，而且这个错误在样例上通常不会触发，只有提交到空测试用例才炸。第二是第 5 步的收尾，前面已经强调过。第三是第 4 步的判断必须用当前块的右边界curR去比，而不是用上一个区间的右端点。区别在哪？如果用一个被包含的小区间作为参照物，比如[1,10]后面跟了[2,3]，用[2,3]的右端点去比下一个区间，就会误判成断开。这类错误在小数据上很难发现，一定要拿一组带包含关系的数据自测。

3.2 C++ 版本：pair 默认排序的便利

#include <bits/stdc++.h> using namespace std; vector<pair<int, int>> mergeIntervals(vector<pair<int, int>> a) { vector<pair<int, int>> res; if (a.empty()) return res; // 空输入必须先挡掉 sort(a.begin(), a.end()); // pair 默认先比 first，再比 second int curL = a[0].first, curR = a[0].second; for (size_t i = 1; i < a.size(); ++i) { if (a[i].first <= curR) { // 相接视为重叠，闭区间用 <= curR = max(curR, a[i].second); // 被包含的情况在这里被自然吸收 } else { res.push_back({curL, curR}); // 当前块已完整，落盘 curL = a[i].first; curR = a[i].second; } } res.push_back({curL, curR}); // 收尾，最后一块 return res; }

C++ 用pair<int, int>的好处是sort默认就按字典序排，省掉自己写比较函数的麻烦，也就避开了比较函数写错这个坑。参数用值传递vector<pair<int,int>> a是有意的，因为内部要排序，传引用会把调用方的数据顺序打乱。如果确实不希望发生拷贝，可以传const引用然后在函数内部另建一份副本，但绝大多数场景下直接值传递更省心。另外注意循环从i = 1开始，因为第 0 个已经被当作初始块了。

3.3 Python 版本：显式指定 key 更稳

def merge_intervals(intervals): if not intervals: return [] # 显式指定 key，避免按元组第二位排序带来的心智负担 intervals.sort(key=lambda x: x[0]) res = [] cur_l, cur_r = intervals[0] for l, r in intervals[1:]: if l <= cur_r: # 闭区间，相接算重叠 if r > cur_r: cur_r = r else: res.append([cur_l, cur_r]) cur_l, cur_r = l, r res.append([cur_l, cur_r]) return res

Python 这里有个细节值得说。如果直接intervals.sort()，元组会按第一位、第二位依次比较，效果上等同于按左端点升序、右端点升序，结果其实也是对的。但显式写key=lambda x: x[0]有两点好处：一是意图明确，读代码的人一眼就知道排序依据是什么；二是当区间不是元组而是列表、或者结构更复杂（比如带权重的区间）时，默认排序可能会因为元素不可比较而直接报错。我现在的习惯是不管什么语言，排序键都写全，宁可多敲几个字符。

还有一点：intervals.sort()是原地排序，会修改传入的列表。如果调用方之后还要用原始顺序，记得先拷一份intervals[:]。这个坑在函数式风格的项目里踩过不止一次。

3.4 Java 版本：比较函数别写成减法

public int[][] merge(int[][] intervals) { if (intervals == null || intervals.length == 0) { return new int[0][]; } // 用 Integer.compare，不要写 (a, b) -> a[0] - b[0] Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0])); List<int[]> res = new ArrayList<>(); int curL = intervals[0][0]; int curR = intervals[0][1]; for (int i = 1; i < intervals.length; i++) { if (intervals[i][0] <= curR) { curR = Math.max(curR, intervals[i][1]); } else { res.add(new int[]{curL, curR}); curL = intervals[i][0]; curR = intervals[i][1]; } } res.add(new int[]{curL, curR}); return res.toArray(new int[res.size()][]); }

Java 这段代码里那个比较函数是重点。很多人图省事写(a, b) -> a[0] - b[0]，在坐标范围不大的时候没问题，但如果左端点的取值接近整型边界，比如一个是一千多万、另一个是负的一千多万，相减就直接溢出，结果是负数，排序顺序就乱了。Integer.compare内部用的是比较而不是相减，不存在这个问题。同理long类型用Long.compare。这个坑平时遇不到，一到压测数据或者极端用例上就现形，属于典型的"知道就没事、不知道就抓瞎"。

另外toArray那行传了一个new int[res.size()][]作为参数，这不是多余的，它告诉 JVM 返回数组的确切类型，避免内部再做一次类型判断。虽然现代 JVM 上性能差异微乎其微，但类型安全上更清晰。

4. 例题实战：四类变形题的做法

4.1 模板题：合并所有重叠区间

最基础的一题，输入一个区间数组，要求合并后输出。直接用上面的代码即可，需要注意两个常见额外要求：一是输出的区间必须按左端点升序，这个排序已经保证了；二是有些变体要求输出区间的总长度之和，那就不要在合并后遍历所有结果区间的长度相加——虽然那样也行，但更省事的做法是在合并过程中直接累加：每次落盘一块的时候加上curR - curL，最后收尾时再补上最后一块的长度。这样省掉一次遍历，也避免了长度计算的重复。

还有一个小变体是"输出合并后的区间个数"。这个更简单，就是在每次落盘时把计数器加一，最后再加一。有经验的人会意识到，区间个数实际上等于断开点的数量加一，这跟后面的最小覆盖问题有点关系。

4.2 变形一：插入一个新区间

题目给一组已经排好序、互不重叠的区间，再给一个新区间，要求把新区间插进去并合并。这题有两条路。

第一条路是省事的写法：把新区间加到原数组末尾，然后整体跑一遍标准合并。时间复杂度 O(n log n)，能过题，但没利用到"原数组已经有序"这个条件，属于浪费。

第二条路是充分利用有序性，做到 O(n)。做法是把原区间按与新区间的位置关系分成三段：

• 完全在新区间左边：r < newL，这些区间跟新区间不相交，直接原样输出；
• 与新区间有交集：l <= newR && r >= newL，这些区间需要跟新区间合并，最终合并成一个区间，左边界取所有参与合并区间左端点的最小值，右边界取所有参与合并区间右端点的最大值；
• 完全在新区间右边：l > newR，原样输出。

因为原数组已经有序，这三段是连续排列的，一次遍历就能分完。注意第一段的判断要用严格小于newL，第三段的判断要用严格大于newR，中间剩下的就是要合并的那一批。这里的严格性很关键，如果写成<=，端点相接时就会被错划到左右两段，导致漏合并。

4.3 变形二：最少区间覆盖目标段

这题的问法通常是：给一组区间和一个目标区间[S, T]，问最少的多少个区间可以完全覆盖目标区间，覆盖不了就返回 -1。思路是贪心，但贪心的方式跟区间合并不完全一样。

先把区间按左端点排序，然后维护一个"当前已经覆盖到的右边界"covered，初始等于S。每一轮，在所有左端点<= covered的区间里，挑一个右端点最大的，用它去拓展covered。如果某一轮找不到任何左端点小于等于covered的区间，说明中间出现了断档，直接返回 -1。如果某一轮拓展后covered >= T，说明覆盖完成，返回使用的区间数。

这里最容易写错的是循环的边界控制。因为是"一轮里考察一批区间"，需要用两层循环：外层控制轮次，内层用指针j扫过所有符合条件的区间。指针j不能在内层循环结束后回退，否则复杂度会退化。这个题在我看来是区间类问题里最能检验是否真正理解排序加扫描思想的一道，建议自己手写一遍再对照。

4.4 变形三：不相交区间的最大化选择

还有一类题跟区间合并正好相反：要求删掉最少的区间，让剩下的区间互不重叠。这道题的经典解法是按右端点升序排序，而不是左端点。原因很直观：右端点越小，留给后面区间的空间就越大，所以每次贪心地选右端点最小的那个，能选就选。

这个例子值得单独拎出来说，因为它提醒我们：区间类问题的排序键没有银弹，取决于你贪心的目标是什么。合并问题关心"能不能接上"，所以看左端点；选择问题关心"留多少空间"，所以看右端点。我见过不少人在两道题之间直接套模板，把排序键换了没换判断条件，结果样例能过、隐藏用例全挂。

5. 三个最容易翻车的细节与排查思路

5.1 排错第一条：输出的最后一块去哪了

这是区间合并最高频的 bug，没有之一。现象是：给的测试数据里，最后一个区间如果跟前面的合并了，结果看起来正常；如果最后一个区间是独立的，它就从输出里凭空消失了。原因是落盘动作只写在else分支里，最后一个区间既没有触发else（因为没有下一个区间跟它比较），也没有单独收尾。

排查方法很简单，构造一组数据，让最后一块必须独立落盘，比如 [[1,2], [5,6]]。如果输出只有 [[1,2]]，那就是漏了收尾。修复就是在循环结束后补一句 push。

顺带说，如果题目要求输出的是"合并后的区间个数"而不是具体区间，这个 bug 表现为数字少了一。所以看到答案差 1 的时候，第一反应就该是去检查收尾逻辑。

5.2 第二个大坑：排序被打乱或者根本没排

现象是结果里出现本该合并却没合并的区间，而且顺序看着乱。常见原因有三种：一是在排序之后又对原数组做了修改，破坏了有序性；二是排序键写错，比如写成了按右端点排但判断逻辑还是按左端点那套；三是多线程环境或者共享了同一个数组，别人把顺序改了。

我的做法是在排序之后、扫描之前，加一句调试输出把排序后的序列打出来，一眼就能看出排序有没有生效。这一步看起来很笨，但比打断点逐步跟踪快得多，尤其在做题环境里没有调试器的时候。

5.3 第三个大坑：坐标范围超出预期

如果题目给的坐标范围达到 10^9 甚至更大，有两件事必须注意。第一，所有跟端点相关的运算都要检查是否会溢出，中间量用long long或者 64 位整数更稳妥。第二，不要用布尔数组去标记覆盖——这正是很多人下意识想到的"暴力涂色法"，它在坐标小的时候很好用，但坐标一大就完全不可行。

说到涂色法，其实它是一个很好的对拍工具。它的逻辑是：开一个布尔数组，把每个区间覆盖到的位置全部标记为真，然后从左到右扫一遍，把连续的标记段输出成区间。这个方法时间复杂度是 O(n * 区间平均长度)，只适合小范围数据，但胜在逻辑简单、几乎不可能写错。写完正解之后，随机生成小范围的区间数据，用涂色法作为参考答案对拍几百组，能揪出绝大多数边界错误。这个对拍思路我自己用了很多年，尤其适合区间、离散化、坐标压缩这一类题目。

def brute_force(intervals, max_coord=50): """小坐标暴力法，仅用于对拍验证，区间为闭区间 [l, r]""" marked = [False] * (max_coord + 2) for l, r in intervals: for x in range(l, r + 1): marked[x] = True res = [] start = None for x in range(max_coord + 2): if marked[x] and start is None: start = x elif not marked[x] and start is not None: res.append([start, x - 1]) start = None return res

这个函数配上随机数据生成器，基本上十分钟就能把正解的可信度拉起来。数据生成的时候记得让坐标范围小一点（比如 0 到 30），否则涂色法会很慢；同时把区间长度也随机化，让长短区间混合出现，这样更容易触发包含关系这一类边界。

5.4 调试顺序建议

真遇到错误的时候，我一般按这个顺序排查，效率最高：

1. 先确认空输入和只有一个区间的输入是否正常，这能排掉大部分初始化问题；
2. 再看排序是否生效，把排序后的序列打出来；
3. 检查判断条件用的是不是curR而不是别的变量，以及不等号方向；
4. 检查收尾是否执行；
5. 最后才怀疑坐标溢出和类型问题。

这个顺序的依据是"概率从高到低"。前面几项是逻辑错误，占了绝大多数；后面几项是环境问题，出现频率低但更难查。

6. 从模板题延伸到真实场景里的用法

6.1 日程冲突与空闲时间计算

日历类应用里，判断"这个时间段能不能开会"本质上就是区间合并加一次查询。把所有已占用时段合并成一组互不相交的区间，然后看候选时间段是否落在任何一段里面；如果要找空闲时段，就是把工作时间和已占用时段做个反向计算——把已占用时段合并，然后在工作时间段里挖掉这些块，剩下的就是空闲。

这里有个业务上的细节：会议时段的端点相接通常不算冲突，比如一个会议 10:00 结束、另一个 10:00 开始，实际是允许的。所以在日程场景里，判断条件应该用<而不是<=，也就是半开区间的语义。这跟我前面说的"端点相接算不算重叠"是同一件事，只是在不同业务里的答案不一样。

6.2 内存段与文件碎片的合并

内存管理里有一类常见操作叫"空闲块合并"：当一块内存被释放后，如果它的前后邻居也是空闲的，就要把它们合成更大的一块，避免碎片化。这其实是一个动态版本的区间合并——每次插入或删除一段，都要检查相邻块的连续性并合并。

它的实现跟静态版本不太一样，通常用有序结构（平衡树或跳表）来维护空闲块，插入新块时找前驱和后继，判断能否接上，能就合并。静态的排序加扫描在这里不适用，因为数据在不断变化。但核心的判断逻辑，也就是"左端点是否小于等于前一块的右边界"，是完全一致的。理解了静态版本，再看这类动态版本就只是数据结构的选择问题。

6.3 日志与文本处理中的段落归并

处理代码差异或者文本变更记录的时候，工具会把有改动的行号区间记录下来。相邻或重叠的改动区域通常在展示前会被合并成一个大块，这样阅读体验更好。这跟区间合并是同一个操作：把行号区间排序后合并，得到若干个独立的变更块。

我在处理日志聚合时也遇到过类似需求：把同一批请求的时间戳按秒聚合成连续的时间段，再统计每个时段内的请求量。这时候区间合并只是前半步，后半步是把每个合并后的区间作为分组键去做聚合。用合并后的区间做分组，比按固定时间窗口切分要更贴合实际的数据分布——数据密集的地方窗口就短，稀疏的地方窗口就长。

6.4 什么时候不该用区间合并

最后说一个反向的经验。区间合并的前提是这些区间可以被"揉"成连续的一段，因为它默认中间没有空洞。如果业务上需要保留区间内部的空洞信息，比如"这个时间段内用户在线了 3 次、每次 5 分钟、中间隔了 10 分钟"，那合并成一个 25 分钟的大段就把信息丢掉了。这种情况下应该保留原始区间列表，改用其他统计方式。

还有一种情况是区间带有除左右端点之外的其他属性，比如每个区间有个权重或者来源标签。合并之后这些属性怎么处理？如果不同区间的属性不同，合并出来的区间属性就变得没有意义。这时候要么先按属性分组再分别合并，要么干脆不合并，直接用空间索引结构去回答查询。**判断该不该合并的标准只有一条：合并后的区间能不能支撑你后面的查询。**如果合并会丢信息，或者下游查询需要原始粒度，那就别合。

我在实际项目里定这条规则的方式很简单：写合并逻辑之前，先写下"合并后我会拿这组区间去做什么"。如果那句话里不需要知道区间的来源和内部结构，就放心合并；否则就得再想想。