插入区间 图解题解
这道题到底在问什么
- 输入
- intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]] ，newInterval = [4,8]
- 输出
- [[1,2],[3,10],[12,16]]（中间一串被 [4,8] 串成一段）
最优解：一步一步想明白
- 3三段式：左边不沾的先收 → 中间重叠的全吃进新区间 → 右边不沾的，先放合并好的新区间再收尾。下面一帧帧套。
- 4准备插入新区间 [4,8]。结果列表现在是空的，指针还没出发，下面逐格判断。
- 5指针走到第 0 个区间 [1,2]，准备和当前新区间 [4,8] 比较位置关系。
- 6它整个在新区间左边，互不相干，归第一类。
- 7第一类：不沾边，原样收进结果（标绿的就是已收进结果的）。新区间还没动。
- 8指针走到第 1 个区间 [3,5]，准备和当前新区间 [4,8] 比较位置关系。
- 9它和新区间挨上了，要被吃进去，归第二类。
- 10第二类：把 [3,5] 吃进新区间（标红表示正被合并）。新区间左端取更小、右端取更大，变成 [3,8]，越合越大。
- 11指针走到第 2 个区间 [6,7]，准备和当前新区间 [3,8] 比较位置关系。
- 12它和新区间挨上了，要被吃进去，归第二类。
- 13第二类：把 [6,7] 吃进新区间（标红表示正被合并）。新区间左端取更小、右端取更大，变成 [3,8]，越合越大。
- 14指针走到第 3 个区间 [8,10]，准备和当前新区间 [3,8] 比较位置关系。
- 15它和新区间挨上了，要被吃进去，归第二类。
- 16第二类：把 [8,10] 吃进新区间（标红表示正被合并）。新区间左端取更小、右端取更大，变成 [3,10]，越合越大。
- 17指针走到第 4 个区间 [12,16]，准备和当前新区间 [3,10] 比较位置关系。
- 18它整个在新区间右边，合并阶段到此结束，归第三类。
- 19遇到右边不沾的区间，说明新区间已经合完了。先把合并好的 [3,10] 放进结果，再继续收剩下的。
- 20第三类：它在新区间右边，原样收进结果（标绿）。后面的也都这样收完。
- 21指针走到第 5 个区间 [18,20]，准备和当前新区间 [3,10] 比较位置关系。
- 22它整个在新区间右边，合并阶段到此结束，归第三类。
- 23第三类：它在新区间右边，原样收进结果（标绿）。后面的也都这样收完。
- 24指针走到第 6 个区间 [22,25]，准备和当前新区间 [3,10] 比较位置关系。
- 25它整个在新区间右边，合并阶段到此结束，归第三类。
- 26第三类：它在新区间右边，原样收进结果（标绿）。后面的也都这样收完。
- 27扫描结束。最终答案是 [1,2] [3,10] [12,16] [18,20] [22,25]，中间那串被 [4,8] 串成了 [3,10]。
⚠️ 容易写错的地方
✗ 错：用 < 判重叠，漏掉刚好挨着的区间
✓ 对：重叠条件用 iv[i][0] <= newInterval[1]
像 [1,2] 和 [2,3] 端点相接也要合并，用严格小于会把它们当成不相交
✗ 错：合并时只更新右端，忘了更新左端
✓ 对：左端取 min、右端取 max
新区间可能比当前原区间起点更靠右，左端必须取两者更小的，否则会丢掉前面一截
✗ 错：三段处理后忘了把新区间放进结果
✓ 对：合并循环结束后一定 append 新区间
新区间是被「吃」大的，它本身不在原数组里，不显式收进结果就漏了
完整代码（Python / C++ / Java）
Python
def insert(intervals, newInterval):
res, i, n = [], 0, len(intervals)
# 1) 左边不重叠的：原样收
while i < n and intervals[i][1] < newInterval[0]:
res.append(intervals[i]); i += 1
# 2) 重叠的：吃进 newInterval
while i < n and intervals[i][0] <= newInterval[1]:
newInterval[0] = min(newInterval[0], intervals[i][0])
newInterval[1] = max(newInterval[1], intervals[i][1])
i += 1
res.append(newInterval)
# 3) 右边不重叠的：原样收
while i < n:
res.append(intervals[i]); i += 1
return resC++
vector<vector<int>> insert(vector<vector<int>>& iv,
vector<int>& ni){
vector<vector<int>> res; int i=0, n=iv.size();
while(i<n && iv[i][1] < ni[0]) res.push_back(iv[i++]);
while(i<n && iv[i][0] <= ni[1]){
ni[0]=min(ni[0],iv[i][0]);
ni[1]=max(ni[1],iv[i][1]); i++;
}
res.push_back(ni);
while(i<n) res.push_back(iv[i++]);
return res;
}Java
public int[][] insert(int[][] iv, int[] ni){
List<int[]> res = new ArrayList<>();
int i=0, n=iv.length;
while(i<n && iv[i][1] < ni[0]) res.add(iv[i++]);
while(i<n && iv[i][0] <= ni[1]){
ni[0]=Math.min(ni[0],iv[i][0]);
ni[1]=Math.max(ni[1],iv[i][1]); i++;
}
res.add(ni);
while(i<n) res.add(iv[i++]);
return res.toArray(new int[0][]);
}复杂度
时间
O(n)
三个 while 合起来恰好把每个区间访问一次，n 是原区间个数
空间
O(n)
除返回的结果列表外只用常数变量；结果本身最多装 n+1 个区间
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 插入区间 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么可以一趟线性扫描，而不用排序？+
因为题目保证原区间已经按起点升序且两两不重叠。新区间影响的只是连续的一段，扫一遍把这段合掉即可，无需额外排序。
如果新区间和所有原区间都不重叠会怎样？+
它会被插到正确位置：左边不沾的先收，遇到第一个起点比它右端还大的区间时，把新区间单独放进结果，再收剩下的。结果仍然有序。
合并那一步为什么左端取 min、右端取 max？+
合并是把两段并成一段，并集的左端是两个左端里更小的，右端是两个右端里更大的，这样才能把整片覆盖住。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 插入区间 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。