京公网安备11010502063487号给定一个已经按起点排好序、互不重叠的区间列表，再插入一个新区间，必要时合并，返回仍然有序且互不重叠的列表。因为原列表已经有序，不需要重新排序，一遍扫描就够：先把完全在新区间左边的区间原样保留；再把与新区间有重叠的全部合并进新区间；最后把完全在新区间右边的原样保留。本文用真实数据展示一个很容易漏掉的边界（新区间放在哪里），实测线性扫描与"放进去再重新合并"的耗时，给出五种语言的实现，并把三段式扫描做成分步演示。
完整题目见官方页面（链接在文末）。原列表有序且互不重叠。基准解是把新区间放进列表，排序，再按上一题"合并区间"的办法重新合并，与三段式扫描是两种不同的写法。一共 12 组用例，覆盖：官方两个示例、原列表为空、新区间被完全包含、新区间在最前、在最后、与一个区间端点相接、与所有区间重叠、点区间：
输入 [[[1,3],[6,9]],[2,5]] 输出 [[1,5],[6,9]] 输入 [[[1,2],[3,5],[6,7],[8,10],[12,16]],[4,8]] 输出 [[1,2],[3,10],[12,16]] 输入 [[],[5,7]] 输出 [[5,7]] 输入 [[[1,5]],[2,3]] 输出 [[1,5]] 输入 [[[1,5]],[6,8]] 输出 [[1,5],[6,8]] 输入 [[[1,5]],[0,0]] 输出 [[0,0],[1,5]]
三段式扫描里，合并完成后必须把（合并后的）新区间放进结果，不管它有没有与任何区间重叠。一个容易写错的做法是：只在遇到第一个"在新区间右边的区间"时才顺手插入新区间。这样当新区间在所有区间的最右边，或者被别的区间完全包含、或者原列表为空时，新区间会丢掉。下面是这种写法的真实结果：
# 只在遇到「右边的区间」时才插入新区间的写法 [[1, 3], [6, 9]] + [2, 5]: 该写法 -> [[1, 5], [6, 9]] solve -> [[1, 5], [6, 9]] [[1, 5]] + [6, 8]: 该写法 -> [[1, 5]] solve -> [[1, 5], [6, 8]] [[1, 5]] + [2, 3]: 该写法 -> [] solve -> [[1, 5]] [] + [5, 7]: 该写法 -> [] solve -> [[5, 7]] [[3, 5], [12, 15]] + [6, 6]: 该写法 -> [[3, 5], [6, 6], [12, 15]] solve -> [[3, 5], [6, 6], [12, 15]]
[[1, 5]] + [6, 8]：新区间在最右边，那个写法得到 [[1, 5]]，[6, 8] 丢了；[[1, 5]] + [2, 3] 与 [] + [5, 7] 更糟，得到的是空列表，原来的区间也一起消失了（合并进新区间之后没有被重新放回）。第一组和最后一组两个写法碰巧相同，是因为那时新区间的右边刚好还有区间，能触发插入。所以这个错误在新区间位于最右边或者列表为空时暴露。
i 是扫描位置，[s, e] 是当前的新区间。第一段：intervals[i][1] < s（终点小于新区间起点）的区间完全在左边，原样加入结果。第二段：intervals[i][0] <= e（起点不超过新区间终点）的区间与新区间重叠，把 s 取成两个起点里较小的，e 取成两个终点里较大的。第二段结束后把 [s, e] 加入结果。第三段：剩下的区间完全在右边，原样加入。Python、Java、Go、JavaScript、C++ 都是真实编译运行的。
Python · 解法代码def solve(intervals, new_interval): res = [] i, n = 0, len(intervals) s, e = new_interval while i < n and intervals[i][1] < s: # 1) 完全在新区间左边（终点 < 新区间起点）的，原样保留 res.append(intervals[i]) i += 1 while i < n and intervals[i][0] <= e: # 2) 与新区间有重叠的，全部合并进新区间 s = min(s, intervals[i][0]) e = max(e, intervals[i][1]) i += 1 res.append([s, e]) # 合并后的新区间（即使一个都没重叠，也要放进去） while i < n: # 3) 完全在新区间右边的，原样保留 res.append(intervals[i]) i += 1 return res
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [[[1,3],[6,9]],[2,5]] → [[1,5],[6,9]] [[[1,2],[3,5],[6,7],[8,10],[12,16]],[4,8]] → [[1,2],[3,10],[12,16]] [[],[5,7]] → [[5,7]] [[[1,5]],[2,3]] → [[1,5]] [[[1,5]],[6,8]] → [[1,5],[6,8]] [[[1,5]],[0,0]] → [[0,0],[1,5]]
Java · 解法代码class Solution { public int[][] insert(int[][] intervals, int[] newInterval) { List<int[]> res = new ArrayList<>(); int i = 0, n = intervals.length; int s = newInterval[0], e = newInterval[1]; while (i < n && intervals[i][1] < s) res.add(intervals[i++]); // 1) 完全在新区间左边的，原样保留 while (i < n && intervals[i][0] <= e) { // 2) 与新区间有重叠的，全部合并进新区间 s = Math.min(s, intervals[i][0]); e = Math.max(e, intervals[i][1]); i++; } res.add(new int[]{s, e}); // 合并后的新区间（即使一个都没重叠，也要放进去） while (i < n) res.add(intervals[i++]); // 3) 完全在新区间右边的，原样保留 return res.toArray(new int[0][]); } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [[[1,3],[6,9]],[2,5]] → [[1,5],[6,9]] [[[1,2],[3,5],[6,7],[8,10],[12,16]],[4,8]] → [[1,2],[3,10],[12,16]] [[],[5,7]] → [[5,7]] [[[1,5]],[2,3]] → [[1,5]] [[[1,5]],[6,8]] → [[1,5],[6,8]] [[[1,5]],[0,0]] → [[0,0],[1,5]]
Go · 解法代码func insert(intervals [][]int, newInterval []int) [][]int { res := [][]int{} i, n := 0, len(intervals) s, e := newInterval[0], newInterval[1] for i < n && intervals[i][1] < s { // 1) 完全在新区间左边的，原样保留 res = append(res, intervals[i]) i++ } for i < n && intervals[i][0] <= e { // 2) 与新区间有重叠的，全部合并进新区间 if intervals[i][0] < s { s = intervals[i][0] } if intervals[i][1] > e { e = intervals[i][1] } i++ } res = append(res, []int{s, e}) // 合并后的新区间（即使一个都没重叠，也要放进去） for i < n { // 3) 完全在新区间右边的，原样保留 res = append(res, intervals[i]) i++ } return res }
$ go build -o bin . && ./bin < cases.jsonl [[[1,3],[6,9]],[2,5]] → [[1,5],[6,9]] [[[1,2],[3,5],[6,7],[8,10],[12,16]],[4,8]] → [[1,2],[3,10],[12,16]] [[],[5,7]] → [[5,7]] [[[1,5]],[2,3]] → [[1,5]] [[[1,5]],[6,8]] → [[1,5],[6,8]] [[[1,5]],[0,0]] → [[0,0],[1,5]]
JavaScript · 解法代码function insert(intervals, newInterval) { const res = []; let i = 0; const n = intervals.length; let [s, e] = newInterval; while (i < n && intervals[i][1] < s) res.push(intervals[i++]); // 1) 完全在新区间左边的，原样保留 while (i < n && intervals[i][0] <= e) { // 2) 与新区间有重叠的，全部合并进新区间 s = Math.min(s, intervals[i][0]); e = Math.max(e, intervals[i][1]); i++; } res.push([s, e]); // 合并后的新区间（即使一个都没重叠，也要放进去） while (i < n) res.push(intervals[i++]); // 3) 完全在新区间右边的，原样保留 return res; }
$ node run.js < cases.jsonl [[[1,3],[6,9]],[2,5]] → [[1,5],[6,9]] [[[1,2],[3,5],[6,7],[8,10],[12,16]],[4,8]] → [[1,2],[3,10],[12,16]] [[],[5,7]] → [[5,7]] [[[1,5]],[2,3]] → [[1,5]] [[[1,5]],[6,8]] → [[1,5],[6,8]] [[[1,5]],[0,0]] → [[0,0],[1,5]]
C++ · 解法代码#include <algorithm> #include <vector> using namespace std; class Solution { public: vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) { vector<vector<int>> res; size_t i = 0, n = intervals.size(); int s = newInterval[0], e = newInterval[1]; while (i < n && intervals[i][1] < s) res.push_back(intervals[i++]); // 1) 完全在新区间左边的，原样保留 while (i < n && intervals[i][0] <= e) { // 2) 与新区间有重叠的，全部合并进新区间 s = min(s, intervals[i][0]); e = max(e, intervals[i][1]); i++; } res.push_back({s, e}); // 合并后的新区间（即使一个都没重叠，也要放进去） while (i < n) res.push_back(intervals[i++]); // 3) 完全在新区间右边的，原样保留 return res; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [[[1,3],[6,9]],[2,5]] → [[1,5],[6,9]] [[[1,2],[3,5],[6,7],[8,10],[12,16]],[4,8]] → [[1,2],[3,10],[12,16]] [[],[5,7]] → [[5,7]] [[[1,5]],[2,3]] → [[1,5]] [[[1,5]],[6,8]] → [[1,5],[6,8]] [[[1,5]],[0,0]] → [[0,0],[1,5]]
共 12 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 12/12 Java 通过 12/12 Go 通过 12/12 JavaScript 通过 12/12 C++ 通过 12/12
已有区间个数 n 分别为 1000、1 万、10 万、100 万，新区间落在最右边（不与任何区间重叠，这样三段式要扫描完整个列表），每个规模取三次中最快的一次：
已有区间个数 n | 暴力解 | 本文解法
1000 | 0.152 ms | 0.054 ms
10000 | 1.961 ms | 0.461 ms
100000 | 35.249 ms | 4.868 ms
1000000 | 581.451 ms | 52.179 ms本文解法是线性的：从 10 万到 100 万（10 倍）增长约 10.7 倍。基准（放进去、排序、重新合并）也是接近线性，因为 Python 的排序会识别已经有序的输入；100 万时基准 581.5ms，三段式 52.2ms，约 11 倍，差异主要来自基准要多做一次排序和重新合并。
Python 版本另外和基准做了随机对拍：0 到 5 个互不重叠的有序区间，新区间随机出现在最前、最后、中间，并可能与多个区间重叠：
随机对拍 20000 组（0 到 5 个互不重叠的有序区间，新区间起点 0 到 40、长度 0 到 12（会落在最前、最后、中间，可能与多个区间重叠）），solve 与 brute 的结果全部一致。
另外四种语言只在上面 12 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用官方示例：[[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]] 中插入 [4, 8]。[1, 2] 的终点 2 小于 4，完全在左边，保留；[3, 5]、[6, 7]、[8, 10] 依次与新区间重叠，新区间先变成 [3, 8]，最后变成 [3, 10]；[12, 16] 完全在右边，保留。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。