LeetCode 57. 插入区间

2026-01-26 HGNULB 约 5 分钟

文章信息 13 个分类 1 个标签

分类

LeetCode CodeTop 中等未解决 10-20 字节跳动快手腾讯猿辅导滴滴华为亚马逊面试经典 150 题

题目描述

✅ 57. 插入区间

题意分析

给定一个区间列表 intervals，每个元素是一个闭区间 [start, end]。再给一个新区间 newInterval，要求把它插进去，使得最终列表里的区间仍然互不重叠、仍然按起点升序排列。

题面里有两个必须抓住的前提，它们决定了这题能有线性解法：原列表已经按左端点排好序，并且原列表中的区间两两互不重叠。这两条不是提示，是题目的硬约束。它们合起来意味着，原列表的右端点也是严格递增的——因为任意相邻两段既不重叠又按左端点有序，前一段必然整个落在后一段左边。

另一个关键语义是「闭区间」。[1, 4] 和 [4, 5] 共享端点 4，它们不是分离的两段，而应当合成 [1, 5]。所以判断「有交集」的门槛是 <= 而不是 <，这个细节几乎是本题最高频的翻车点。

约束方面：区间个数可以是 0，也就是原列表可能为空，此时答案就是只含新区间的列表；端点是带符号整数，绝对值到 $10^5$ 量级，不存在溢出压力；题目保证每个区间自身满足 start <= end，新区间也一样，不需要交换端点。

需要单独想清楚的边界：新区间整个落在所有原区间的左边（插到最前）；整个落在右边（追加到最后）；跨度极大、把好几段原区间全吞掉；只与某一段的端点相接；以及原列表为空。

解法：三段扫描合并新区间

核心思路

原区间已经按起点升序排列且互不重叠，因此与新区间相交的区间一定是连续的一段。没有必要重新排序，只需把原数组分成三部分：

右端点小于新区间左端点的区间，原样加入答案；

与新区间相交的连续区间，不断扩张新区间的左右边界；

剩余区间，原样加入答案。

合并阶段的不变量是：[start, end] 始终表示新区间与已扫描重叠区间的并集。由于区间有序，合并完成后，后续区间都在它右侧，不会再产生新的交集。

题目使用闭区间：[1,4] 与 [4,5] 共享端点，必须合并。因此左侧区间的判断用 < start，重叠判断用 <= end。

解题步骤

扫描并收集所有满足 interval[1] < newInterval[0] 的左侧区间。

用新区间初始化 start 和 end。

当下一个区间满足 interval[0] <= end 时，将它合并到 [start, end]。

把合并后的区间加入答案。即使没有发生重叠，这一步也要执行。

追加剩余的右侧区间。

例如 [[1,2],[3,5],[6,7],[8,10],[12,16]] 插入 [4,8]：先保留 [1,2]，中间三段与新区间合成 [3,10]，最后追加 [12,16]。

代码实现

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> result = new ArrayList<>();
        int index = 0;

        while (index < intervals.length && intervals[index][1] < newInterval[0]) {
            result.add(intervals[index++]);
        }

        int start = newInterval[0];
        int end = newInterval[1];
        while (index < intervals.length && intervals[index][0] <= end) {
            start = Math.min(start, intervals[index][0]);
            end = Math.max(end, intervals[index][1]);
            index++;
        }
        result.add(new int[]{start, end});

        while (index < intervals.length) {
            result.add(intervals[index++]);
        }
        return result.toArray(new int[0][]);
    }
}

func insert(intervals [][]int, newInterval []int) [][]int {
    result := make([][]int, 0, len(intervals)+1)
    index := 0

    for index < len(intervals) && intervals[index][1] < newInterval[0] {
        result = append(result, intervals[index])
        index++
    }

    start, end := newInterval[0], newInterval[1]
    for index < len(intervals) && intervals[index][0] <= end {
        if intervals[index][0] < start {
            start = intervals[index][0]
        }
        if intervals[index][1] > end {
            end = intervals[index][1]
        }
        index++
    }
    result = append(result, []int{start, end})

    result = append(result, intervals[index:]...)
    return result
}

复杂度分析

时间复杂度：$O(n)$。下标只向右移动，每个区间恰好处理一次。

空间复杂度：$O(n)$，用于保存返回结果；不计返回值时额外空间为 $O(1)$。

关键点总结

有序且互不重叠的前提，保证相交区间构成连续的一段。

合并条件必须使用动态扩张后的 end，才能连续吞并多个区间。

闭区间端点相等也算相交，所以左侧判断用 <，合并判断用 <=。

新区间无论是否与原区间相交，都必须恰好加入答案一次。

易错点总结

把第一段条件写成 interval[1] <= start，会漏合并端点相接的区间。

合并时只更新右端点，可能丢掉比新区间更靠左的起点。

使用固定的 newInterval[1] 判断重叠，会漏掉合并后新覆盖到的区间。

原数组为空、新区间在最左或最右都不需要特判，循环边界应自然覆盖这些情况。

相似题目

题目	难度	考察点
56. 合并区间	中等	排序后合并区间
435. 无重叠区间	中等	按右端点贪心取不交
986. 区间列表的交集	中等	双指针求区间交集
1288. 删除被覆盖区间	中等	覆盖关系判定
252. 会议室	简单	相邻区间冲突检测
253. 会议室 II	中等	最大区间重叠数
759. 员工空闲时间	困难	多路区间求并后取补
LCR 074. 合并区间	中等	合并区间同题变体