57.插入区间
57. 插入区间
鲁迅曾说：“假期是最让我痛苦的时候，我想偷偷地学吧，看别人都在摆烂，自己也挺不
好意思；我想摆烂吧，一想到自己目前的学习进度，又很不甘心。于是，我规定自己，每
天早上起来学习一会，每天晚上就放肆的玩，我似乎找到了一种平衡。嗯，现在就开始刷
一道 LeetCode 吧：插入区间。”
题意
给你一个 无重叠的，按照区间起始端点排序的区间列表 intervals，其中 intervals[i] =
[starti, endi] 表示第 i 个区间的开始和结束，并且 intervals 按照 starti 升序排列。同样给
定一个区间 newInterval = [start, end] 表示另一个区间的开始和结束。
在 intervals 中插入区间 newInterval，使得 intervals 依然按照 starti 升序排列，且区间之
间不重叠（如果有必要的话，可以合并区间）。
返回插入之后的 intervals。
注意 你不需要原地修改 intervals。你可以创建一个新数组然后返回它。
难度
中等
示例
示例 1：
输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
输出：[[1,5],[6,9]]
示例 2：
输入：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：
输入：intervals = [], newInterval = [5,7]
输出：[[5,7]]
示例 4：
输入：intervals = [[1,5]], newInterval = [2,3]
输出：[[1,5]]
示例 5：
输入：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 加入。
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]]
}
}
来看一下运行结果，还不错。
057.插入区间-20250201102519.png
分析 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])。
按照这个思路，我们可以写出更直观的代码。
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]]
}
}
运行效率也非常不错。
057.插入区间-20250201103123.png
拆解一下。
while (i < n && intervals[i][1] < newInterval[0]) {
result.add(intervals[i]);
i++;
}
这段代码的意思是，如果当前区间的结束位置小于 newInterval 的起始位置，说明当前区
间在 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);
当前区间的 start 小于等于 newInterval[1]，说明有重叠，合并区间。
while (i < n) {
result.add(intervals[i]);
i++;
}
当前区间 interval[i] 在 newInterval 之后，直接加入结果。
总结
本题实际上只是多了一个插入的环节，多加思考，便能迎刃而解。
力扣链接：https://leetcode.cn/problems/insert-interval/
