LeetCode 57. 插入区间

约 5 分钟
文章信息 13 个分类 1 个标签
分类
LeetCode CodeTop 中等 未解决 10-20 面试经典 150 题 腾讯 字节 华为 亚马逊 快手 滴滴 猿辅导
标签
数组

题目描述

✅ 57. 插入区间

image-20260928215247074

image-20260928215247075

题意分析

将一个新区间插入已经按起点排序且互不重叠的闭区间列表，返回仍有序且互不重叠的结果。闭区间包含端点，因此端点相接也要合并。原区间之间没有冲突，只需要找出与新区间相交的一段，不必重新排序。

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

核心思路

[!blue]

用一个下标从左到右扫描，将原区间分成左侧、重叠、右侧三段。先收集右端点小于新区间左端点的区间，它们完全位于新区间左侧，可以直接保留。

用 [start, end] 保存新区间与已遇到重叠区间的并集。左侧区间已经跳过，此后的区间右端点不会再落到新区间左侧；只要当前区间的左端点 <= end，二者就相交。合并时左端取最小值、右端取最大值，随后用更新后的 end 判断下一段，才能保留整个并集的覆盖范围。

一旦当前区间左端点 > end，它与合并区间已经分离。后续区间的起点只会更大，也都不会相交，因此将 [start, end] 加入一次，再原样追加剩余区间即可。已保留的左侧区间与这些原区间本来就互不重叠，所以合并后不会反过来影响左侧结果。

解题步骤

  1. 扫描并收集所有满足 interval[1] < newInterval[0] 的左侧区间。
  2. 用新区间初始化 start 和 end。
  3. 当下一个区间满足 interval[0] <= end 时，令 start 取两者左端点的较小值、end 取右端点的较大值，再推进下标。
  4. 把合并后的区间加入答案。即使没有发生重叠，这一步也要执行。
  5. 追加剩余的右侧区间。原列表为空时，三个扫描循环都跳过，仍会通过第 4 步得到只包含新区间的答案。

代码实现

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)$，其中 $n$ 为原区间数。三个阶段共用一个只向右移动的下标，每个原区间只处理一次。
  • 空间复杂度：$O(n+1)$，用于至多包含 $n+1$ 个区间的结果。Java 还用列表暂存结果引用，Go 直接向预分配的结果切片追加；扫描本身只使用常数个变量。

关键点总结

[!green]

  • 有序且互不重叠的前提，保证相交区间构成连续的一段。
  • 闭区间端点相等也算相交，所以左侧判断用 <，合并判断用 <=。
  • 新区间无论是否与原区间相交，都必须恰好加入答案一次。

易错点总结

[!yellow]

  • 把第一段条件写成 interval[1] <= start，会漏合并端点相接的区间。
  • 合并时 start 取最小、end 取最大，不能丢掉任一侧覆盖范围。
  • 重叠阶段要比较当前的 end；遇到第一个不相交的右侧区间后即可停止合并，不能把余下区间一并扩入新区间。
  • 原数组为空、新区间在最左或最右都不需要特判，循环边界应自然覆盖这些情况。

相似题目

题目 难度 关联与区别
56. 合并区间 中等 原题合并任意区间集合，本题其余区间已有序且不重叠，可只定位新段的重叠范围。
715. Range 模块 困难 同样维护区间并集，原题要持续支持加入、删除与覆盖查询。
986. 区间列表的交集 中等 按起点排序后合并重叠区间；本题把一个新区间并入已有有序区间，该题以双指针枚举两个区间表的交集。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/33159262
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！