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/