京公网安备11010502063487号给定若干个闭区间 [起点, 终点]，把所有有重叠的区间合并，返回合并之后互不重叠的区间。端点相接（例如 [1, 4] 和 [4, 5]）也算重叠，要合并。标准做法是先按起点排序，这样能合并的区间一定挨在一起，然后扫描一遍：当前区间的起点不超过上一个合并区间的终点，就合并，终点取两者较大的；否则作为新区间加入。本文用真实数据展示两种常见错误（忘了排序、终点没取较大值）各自会错多少，实测排序合并与反复两两合并的耗时，给出五种语言的实现，并把合并过程做成分步演示。
完整题目见官方页面（链接在文末）。结果按起点从小到大排列。基准解不排序：反复找一对有重叠的区间合并，直到再也找不到为止，与"排序后扫描"是完全不同的写法。一共 12 组用例，覆盖：官方示例、端点相接、一个区间被另一个完全包含、只有一个区间、点区间（起点等于终点）、输入乱序：
输入 [[[1,3],[2,6],[8,10],[15,18]]] 输出 [[1,6],[8,10],[15,18]] 输入 [[[1,4],[4,5]]] 输出 [[1,5]] 输入 [[[1,4],[0,4]]] 输出 [[0,4]] 输入 [[[1,4],[2,3]]] 输出 [[1,4]] 输入 [[[1,4]]] 输出 [[1,4]] 输入 [[[1,4],[0,0]]] 输出 [[0,0],[1,4]]
排序和"终点取 max"是这道题最常见的两个漏洞。下面是两种错误写法与 solve 在同样数据上的真实结果，最后一行是在 20000 组随机数据上统计的出错比例：
# 两种常见的错误写法 [[1, 4], [0, 2], [3, 5]]: 没排序 -> [[1, 5]]；终点不取 max -> [[0, 5]]；solve -> [[0, 5]] [[8, 10], [1, 3], [2, 6]]: 没排序 -> [[8, 10]]；终点不取 max -> [[1, 6], [8, 10]]；solve -> [[1, 6], [8, 10]] [[1, 10], [2, 3], [4, 5]]: 没排序 -> [[1, 10]]；终点不取 max -> [[1, 3], [4, 5]]；solve -> [[1, 10]] [[1, 4], [2, 3]]: 没排序 -> [[1, 4]]；终点不取 max -> [[1, 3]]；solve -> [[1, 4]] 随机 20000 组：没排序的写法出错 15104 组（75.5%），终点不取 max 的写法出错 6350 组（31.8%）
不排序时，输入乱序就会漏合并：[[8, 10], [1, 3], [2, 6]] 只得到 [[8, 10]]：[1, 3] 的起点 1 不大于 10，被当成有重叠并入了 [8, 10]，但合并时只更新终点、没有更新起点，所以 1 到 6 这一段直接消失了。终点不取 max 时，被完全包含的区间会把终点缩小：[[1, 10], [2, 3], [4, 5]] 得到 [[1, 3], [4, 5]]，而正确结果是 [[1, 10]]。在随机数据上，不排序的写法错了 75.5%，终点不取 max 的写法错了 31.8%，所以这两个错误几乎一定会被随机测试发现，但只用官方示例可能测不出来。
先按起点排序。用一个结果列表，对每个区间：如果结果非空，并且它的起点不超过结果最后一个区间的终点，就说明有重叠，把最后一个区间的终点更新为两个终点里较大的一个；否则把它作为新区间追加。Python、Java、Go、JavaScript、C++ 都是真实编译运行的；Java、Go、C++ 里排序是原地进行的。
Python · 解法代码def solve(intervals): intervals = sorted(intervals, key=lambda x: x[0]) # 按起点排序：能合并的区间一定挨在一起 res = [] for s, e in intervals: if res and s <= res[-1][1]: # 与上一个合并后的区间有重叠（含端点相接） res[-1][1] = max(res[-1][1], e) # 终点取较大者：被完全包含时终点不能变小 else: res.append([s, e]) return res
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [[[1,3],[2,6],[8,10],[15,18]]] → [[1,6],[8,10],[15,18]] [[[1,4],[4,5]]] → [[1,5]] [[[1,4],[0,4]]] → [[0,4]] [[[1,4],[2,3]]] → [[1,4]] [[[1,4]]] → [[1,4]] [[[1,4],[0,0]]] → [[0,0],[1,4]]
Java · 解法代码class Solution { public int[][] merge(int[][] intervals) { Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0])); // 按起点排序：能合并的区间一定挨在一起 List<int[]> res = new ArrayList<>(); for (int[] it : intervals) { if (!res.isEmpty() && it[0] <= res.get(res.size() - 1)[1]) { // 与上一个合并后的区间有重叠（含端点相接） int[] last = res.get(res.size() - 1); last[1] = Math.max(last[1], it[1]); // 终点取较大者：被完全包含时终点不能变小 } else { res.add(new int[]{it[0], it[1]}); } } return res.toArray(new int[0][]); } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [[[1,3],[2,6],[8,10],[15,18]]] → [[1,6],[8,10],[15,18]] [[[1,4],[4,5]]] → [[1,5]] [[[1,4],[0,4]]] → [[0,4]] [[[1,4],[2,3]]] → [[1,4]] [[[1,4]]] → [[1,4]] [[[1,4],[0,0]]] → [[0,0],[1,4]]
Go · 解法代码import "sort" func merge(intervals [][]int) [][]int { sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] }) // 按起点排序：能合并的区间一定挨在一起 res := [][]int{} for _, it := range intervals { if len(res) > 0 && it[0] <= res[len(res)-1][1] { // 与上一个合并后的区间有重叠（含端点相接） if it[1] > res[len(res)-1][1] { // 终点取较大者：被完全包含时终点不能变小 res[len(res)-1][1] = it[1] } } else { res = append(res, []int{it[0], it[1]}) } } return res }
$ go build -o bin . && ./bin < cases.jsonl [[[1,3],[2,6],[8,10],[15,18]]] → [[1,6],[8,10],[15,18]] [[[1,4],[4,5]]] → [[1,5]] [[[1,4],[0,4]]] → [[0,4]] [[[1,4],[2,3]]] → [[1,4]] [[[1,4]]] → [[1,4]] [[[1,4],[0,0]]] → [[0,0],[1,4]]
JavaScript · 解法代码function merge(intervals) { intervals.sort((a, b) => a[0] - b[0]); // 按起点排序：能合并的区间一定挨在一起 const res = []; for (const [s, e] of intervals) { if (res.length > 0 && s <= res[res.length - 1][1]) { // 与上一个合并后的区间有重叠（含端点相接） res[res.length - 1][1] = Math.max(res[res.length - 1][1], e); // 终点取较大者：被完全包含时终点不能变小 } else { res.push([s, e]); } } return res; }
$ node run.js < cases.jsonl [[[1,3],[2,6],[8,10],[15,18]]] → [[1,6],[8,10],[15,18]] [[[1,4],[4,5]]] → [[1,5]] [[[1,4],[0,4]]] → [[0,4]] [[[1,4],[2,3]]] → [[1,4]] [[[1,4]]] → [[1,4]] [[[1,4],[0,0]]] → [[0,0],[1,4]]
C++ · 解法代码#include <algorithm> #include <vector> using namespace std; class Solution { public: vector<vector<int>> merge(vector<vector<int>>& intervals) { sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) { return a[0] < b[0]; }); // 按起点排序：能合并的区间一定挨在一起 vector<vector<int>> res; for (auto& it : intervals) { if (!res.empty() && it[0] <= res.back()[1]) { // 与上一个合并后的区间有重叠（含端点相接） res.back()[1] = max(res.back()[1], it[1]); // 终点取较大者：被完全包含时终点不能变小 } else { res.push_back({it[0], it[1]}); } } return res; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [[[1,3],[2,6],[8,10],[15,18]]] → [[1,6],[8,10],[15,18]] [[[1,4],[4,5]]] → [[1,5]] [[[1,4],[0,4]]] → [[0,4]] [[[1,4],[2,3]]] → [[1,4]] [[[1,4]]] → [[1,4]] [[[1,4],[0,0]]] → [[0,0],[1,4]]
共 12 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 12/12 Java 通过 12/12 Go 通过 12/12 JavaScript 通过 12/12 C++ 通过 12/12
区间个数 n 分别为 100、300、1000、10 万，每个规模取三次中最快的一次。基准解每次要找一对有重叠的区间，最坏是立方级：
区间个数 n | 暴力解 | 本文解法
100 | 2.935 ms | 0.016 ms
300 | 53.078 ms | 0.047 ms
1000 | 1717.793 ms | 0.167 ms
100000 | （未测，太慢） | 31.160 ms基准解从 100 到 300（3 倍）耗时增长约 18 倍，从 300 到 1000 增长约 32 倍，增长很快；n = 1000 时基准用了 1717.8ms，本文解法只用了 0.167ms。基准在 n = 10 万时没有再测。本文解法从 1000 到 10 万（100 倍）增长约 187 倍，略高于 O(n log n) 的预期，我没有细究。
Python 版本另外和反复两两合并的基准做了随机对拍，包括点区间、端点相接、包含关系：
随机对拍 20000 组（1 到 8 个区间，起点取 0 到 20、长度取 0 到 6（含点区间、端点相接、包含关系）），solve 与 brute 的结果全部一致。
另外四种语言只在上面 12 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用 [[8, 10], [1, 3], [15, 18], [2, 6]]（输入是乱序的）。先排序得到 [[1, 3], [2, 6], [8, 10], [15, 18]]；[2, 6] 的起点 2 不超过 [1, 3] 的终点 3，合并成 [1, 6]；[8, 10] 和 [15, 18] 都与前一个没有重叠。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。