LeetCode 435. 无重叠区间

约 5 分钟
文章信息 13 个分类 5 个标签
分类
LeetCode CodeTop 中等 未解决 需复习 10-20 字节跳动 微软 腾讯 猿辅导 滴滴 小红书 LeetCode 75
标签
数组 动态规划 排序 贪心 区间问题
目录

题目描述

✅ 435. 无重叠区间

image-20230312180316633

题意分析

输入是一组闭区间，要求删掉数量最少的区间，使剩下的区间两两不重叠；题目明确端点相接不算重叠，也就是 [1,2] 与 [2,3] 可以同时保留。

「删得最少」和「留得最多」是同一件事：总数是固定的，删除数 = 总数 − 最多能保留的互不重叠区间数。把问题转成求最大保留数，条件立刻变得可以逐步维护。

约束信号：区间数量可以到 $10^5$，只能接受 $O(n \log n)$ 级别的处理；端点是普通整数且可能为负，初始值不能随手写 0；输入顺序完全任意，本身没有任何规律可用。

边界包括：只有一个区间时答案是 0；多个区间完全相同；一个长区间套住若干短区间；两个区间恰好端点相接，此时不能判成重叠。

解法：按右端点排序的贪心

核心思路

「删除最少」等价于「保留最多」。能否接入下一个区间只取决于当前结束位置，因此应优先保留右端点最小的区间，为后续留下尽可能大的可选空间。

不变量是：处理完排序后的前若干区间时，已保留数量是该前缀能达到的最大值；在所有同样大小的方案中，end 尽可能小。当前区间若满足 start >= end 就接入；否则它的结束位置不会更早，舍弃它不会让后续选择变差。

正确性可用交换论证：设某个最优方案首先保留区间 b，贪心选出的 a 右端点不晚于 b。用 a 替换 b 后，后续原本能接在 b 后的区间仍能接在 a 后，保留数量不变。对剩余区间重复此过程，就能把某个最优方案转换成贪心方案。

解题步骤

  • 按右端点升序排序，用第一个区间初始化 end。
  • 从第二个区间开始扫描：若 start < end，说明发生重叠，删除数加一；由于当前区间结束得不更早，继续保留原区间。
  • 若 start >= end，两个区间不重叠，保留当前区间并更新 end。端点相接允许共存，所以这里必须用 >=。
  • 扫描结束后返回删除数。

例如 [[1,2],[2,3],[3,4],[1,3]] 按右端点排序后，依次保留 [1,2]、[2,3]，删除与它们冲突的 [1,3]，再保留 [3,4]，答案为 1。

代码实现

import java.util.Arrays;

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
        int removed = 0;
        int end = intervals[0][1];

        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < end) {
                removed++;
            } else {
                end = intervals[i][1];
            }
        }
        return removed;
    }
}

import "sort"

func eraseOverlapIntervals(intervals [][]int) int {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][1] < intervals[j][1]
    })

    removed := 0
    end := intervals[0][1]
    for i := 1; i < len(intervals); i++ {
        if intervals[i][0] < end {
            removed++
        } else {
            end = intervals[i][1]
        }
    }
    return removed
}

复杂度分析

  • 时间复杂度：$O(n \log n)$，排序是 $O(n \log n)$，之后只做一次线性扫描，每个区间常数次比较与赋值，排序占主导。
  • 空间复杂度：贪心扫描为 $O(1)$；若计入标准库排序，Java 的对象数组排序需要 $O(n)$ 辅助空间，Go 排序需要 $O(\log n)$ 调用栈。

关键点总结

  • 把「删除最少」翻译成「保留最多」，问题才有可以逐步维护的状态；这一步转化是本题的分水岭。
  • 排序键必须是右端点：只有结束最早的区间才能保证给后续留下最大空间，按左端点或按长度排序都会被反例打穿。
  • end 是唯一需要维护的状态；发生冲突时保留更早结束的区间。
  • 面试时不仅要写出贪心，还要能用「替换最优解的第一个区间」完成交换论证。
  • 本题端点相接不算重叠，条件是 start >= end；边界口径必须从题意推出。

易错点总结

  • 错误写法：按左端点排序 Arrays.sort(intervals, (a, b) -> a[0] - b[0]) 后照样「能接就接」。用例 [[1,100],[2,3],[3,4]] → 先占住 [1,100]，后面两个都被挡掉，只保留 1 个，返回 2，正确答案是 1。
  • 错误写法：判断重叠写成 interval[0] > end。用例 [[1,2],[2,3]] → 2 > 2 不成立，把端点相接误判为重叠，返回 1，正确答案是 0。
  • 错误写法：保留新区间时忘记更新 end。用例 [[1,2],[2,100],[50,101]] 会把后两个重叠区间都保留，返回 0；正确答案是 1。
  • 错误写法：用 a[1] - b[1] 比较右端点。端点接近整数边界时减法可能溢出，应使用 Integer.compare。
  • 错误写法：删除冲突区间后仍更新 end。用例 [[1,2],[1,3],[2,4]] 会错过本可保留的 [2,4]，多删一个区间。

相似题目

题目 难度 考察点
56. 合并区间 中等 按左端点排序后合并
253. 会议室 II 中等 区间重叠数峰值
452. 用最少数量的箭引爆气球 中等 区间分组打点
1024. 视频拼接 中等 区间覆盖贪心
1288. 删除被覆盖区间 中等 区间包含关系判定
757. 设置交集大小至少为2 困难 排序后构造交集元素