057.插入区间
作者：沉默王二
发布时间：2025-02-01T10:40:33.630+0800
鲁迅曾说：“假期是最让我痛苦的时候，我想偷偷地学吧，看别人都在摆烂，自己也挺不好意思；我想摆烂吧，一想到自己目前的学习进度，又很不甘心。于是，我规定自己，每天早上起来学习一会，每天晚上就放肆的玩，我似乎找到了一种平衡。嗯，现在就开始刷一道 LeetCode 吧：插入区间。”
题意
给你一个 无重叠的，按照区间起始端点排序的区间列表 intervals，其中 intervals[i] = [starti, endi] 表示第 i 个区间的开始和结束，并且 intervals 按照 starti 升序排列。同样给定一个区间 newInterval = [start, end] 表示另一个区间的开始和结束。
在 intervals 中插入区间 newInterval，使得 intervals 依然按照 starti 升序排列，且区间之间不重叠（如果有必要的话，可以合并区间）。
返回插入之后的 intervals。
注意 你不需要原地修改 intervals。你可以创建一个新数组然后返回它。
难度
中等
示例
示例 1：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
输出：[[1,5],[6,9]]
示例 2：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出：[[1,2],[3,10],[12,16]]
解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。
示例 3：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
输入：intervals = [], newInterval = [5,7]
输出：[[5,7]]
示例 4：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
输入：intervals = [[1,5]], newInterval = [2,3]
输出：[[1,5]]
示例 5：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
输入：intervals = [[1,5]], newInterval = [2,7]
输出：[[1,7]]
### 分析 1
这道题的题目虽然是插入区间，但跟 056.合并区间 只差了一个 newInterval。
仔细分析一下就能发现，这道题其实是变相的合并区间，就是把newInterval加入到原有的intervals中。
并且这题也强调了，intervals 是按照起始端点排序的，所以我们只需要找到第一个区间——起始端点在newIntervals的起始端点之后的 intervals[i]，然后将 newInterval 插入到这个 intervals[i] 之前就行。
比如说，intervals = [[1,3],[6,9]]，newInterval = [2,5]，[1,3] 和 [2,5] 发生重叠，合并成 [1,5]。
然后就和 056.合并区间 一模一样了。
由于数组不便修改，我们考虑遍历 intervals 并用 List 记录每个区间，在遇到 newIntervals 的起始端点之后的 intervals[i] 时，就把 newInterval 加入。
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
// 如果 intervals 为空，直接返回 newInterval
if (intervals.length == 0) {
int[][] res = new int[1][2];
res[0] = newInterval;
return res;
}
boolean flag = false; // 标记 newInterval 是否已经插入
List<int[]> prework = new ArrayList<>(); // 存放插入 newInterval 后的区间列表
// 第一步：将 newInterval 插入到正确的位置
for (int[] interval : intervals) {
// 如果 `newInterval` 还未插入，并且当前区间起点大于 `newInterval`，就先插入 `newInterval`
if (!flag && interval[0] > newInterval[0]) {
flag = true;
prework.add(new int[]{newInterval[0], newInterval[1]});
}
// 添加当前区间
prework.add(new int[]{interval[0], interval[1]});
}
// 如果 `newInterval` 还未插入，则说明它比所有区间都大，放到最后
if (!flag) {
prework.add(new int[]{newInterval[0], newInterval[1]});
}
// 第二步：合并区间
List<int[]> ans = new ArrayList<>();
for (int i = 0; i < prework.size(); i++) {
int[] nowPos = prework.get(i); // 当前区间
int lef = nowPos[0], rig = nowPos[1]; // 当前区间的起点和终点
// 当下一个区间的起点小于等于当前终点时，说明有重叠，进行合并
while ((i + 1 < prework.size()) && prework.get(i + 1)[0] <= rig) {
rig = Math.max(rig, prework.get(i + 1)[1]); // 更新终点
i++; // 跳过已合并的区间
}
// 将合并后的区间加入结果列表
ans.add(new int[]{lef, rig});
}
// 第三步：转换 List 为二维数组并返回
return ans.toArray(new int[ans.size()][2]);
}
public static void main(String[] args) {
Solution solution = new Solution();
int[][] intervals = {{1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}};
int[] newInterval = {4, 8};
System.out.println(java.util.Arrays.deepToString(solution.insert(intervals, newInterval)));
// 输出: [[1,2], [3,10], [12,16]]
}
}
来看一下运行结果，还不错。
分析 2
我们再来想一想，如果 newInterval 在当前区间之前（newInterval[1] < interval[0]），说明 newInterval 应该直接插入到当前区间之前，不需要合并。
如果 newInterval 在当前区间之后（newInterval[0] > interval[1]），说明 newInterval 不会影响当前区间，直接加入结果列表。
如果 newInterval 与当前区间有重叠，则合并：newInterval[0] = min(newInterval[0], interval[0])，newInterval[1] = max(newInterval[1], interval[1])。
按照这个思路，我们可以写出更直观的代码。
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
List<int[]> result = new ArrayList<>();
int i = 0, n = intervals.length;
// 1. 处理所有在 newInterval 之前的区间
while (i < n && intervals[i][1] < newInterval[0]) {
result.add(intervals[i]);
i++;
}
// 2. 处理所有与 newInterval 重叠的区间
while (i < n && intervals[i][0] <= newInterval[1]) {
newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
i++;
}
result.add(newInterval); // 插入合并后的区间
// 3. 处理所有在 newInterval 之后的区间
while (i < n) {
result.add(intervals[i]);
i++;
}
// 4. 返回结果
return result.toArray(new int[result.size()][]);
}
public static void main(String[] args) {
Solution solution = new Solution();
int[][] intervals = {{1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}};
int[] newInterval = {4, 8};
System.out.println(java.util.Arrays.deepToString(solution.insert(intervals, newInterval)));
// 输出: [[1,2], [3,10], [12,16]]
}
}
运行效率也非常不错。
拆解一下。
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
while (i < n && intervals[i][1] < newInterval[0]) {
result.add(intervals[i]);
i++;
}
这段代码的意思是，如果当前区间的结束位置小于 newInterval 的起始位置，说明当前区间在 newInterval 之前，直接加入结果列表。
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
while (i < n && intervals[i][0] <= newInterval[1]) {
newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
i++;
}
result.add(newInterval);
当前区间的 start 小于等于 newInterval[1]，说明有重叠，合并区间。
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
while (i < n) {
result.add(intervals[i]);
i++;
}
当前区间 interval[i] 在 newInterval 之后，直接加入结果。
总结
本题实际上只是多了一个插入的环节，多加思考，便能迎刃而解。
力扣链接：https://leetcode.cn/problems/insert-interval/
一步一个脚印
不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。
PDF 版本目前只针对二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 加入我们吧。
一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 7000 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！
语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu
这道题可以说完全重写了，给出 2 道大家完全都能掌握的题解（思路看看新的区间和之前的区间是否有重合，有就合并）。
增加代码注释，这样大家更容易看懂并掌握题解；
增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；
增加手绘图，这样大家更容易理解解题思路；
增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；
增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；
图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。
另外，这一版本会作为 PDF 的终稿随后在星球进行发布。