LeetCode 435. 无重叠区间

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

题目描述

✅ 435. 无重叠区间

image-20260928215236368

image-20260928215236369

题意分析

每个区间只能整体保留或删除，不能通过合并改变它。总区间数固定，因此删除最少区间，等价于保留最多互不重叠的区间。

题目允许端点相接，后一段开始等于前一段结束时仍能保留。为了尽量给后续区间留出位置，每次应从当前能接上的区间里，优先选择结束最早的一个；按右端点升序排序就能依次作出这个选择。

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

核心思路

[!blue]

固定已经保留的区间，设接下来最早结束的可选区间为 a，某个最优方案接下来选择了 b。由于 a、b 都能接上前缀，且 a 的结束位置不晚于 b，将 b 换成 a 后，原本接在 b 后面的区间仍然都能接上。替换不减少保留数量，说明一定存在采用这次贪心选择的最优方案；对后续区间重复这一过程即可。

排序后，end 表示最后一个已保留区间的右端点，removed 表示扫描过程中删除的区间数。已保留的区间互不重叠，所以新区间只需与最后一个比较：

  • 若 start < end，新区间发生重叠。它的结束位置不会比已保留区间更早，删除它并保留原来的 end，更有利于接入后续区间。
  • 若 start >= end，新区间能够接入，而且它是尚未扫描的可接区间中结束最早的一个，保留它并更新 end。

每个区间都恰好被保留或删除一次。贪心保证保留数量最多，因此直接累计得到的 removed 就是最少删除数。右端点相同的区间无需额外规定排序顺序：能接入的任一个留下的结束位置都相同。

解题步骤

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

代码实现

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)$ 调用栈。

关键点总结

[!green]

  • 总数固定，把「删除最少」转成「保留最多」，再用最早结束的区间给后续选择留出空间。
  • 当前贪心依赖右端点升序，交换论证保证每次选取都能延续到某个最优方案。
  • end 记录最后保留的结束位置，removed 累计删除数；冲突时只增加计数，不改结束位置。
  • 本题端点相接不算重叠，条件是 start >= end；边界口径必须从题意推出。

易错点总结

[!yellow]

  • 只把排序改成按左端点升序，再无条件保留最先遇到的区间，可能留下很长的区间并挡住多个短区间；这不符合本解法的贪心依据。
  • 接入条件不能写成 start > end，否则会把允许的端点相接误判成重叠。
  • 保留新区间时必须更新 end；删除冲突区间时必须保留旧 end，否则后续判断会基于错误边界。
  • 区间端点可以是负数，end 应从第一个实际区间初始化，不能默认设为零。
  • 题目保证至少有一个区间，所以可以访问 intervals[0]；只有一个区间时循环不执行，删除数自然为零。

相似题目

题目 难度 关联与区别
452. 用最少数量的箭引爆气球 中等 同样按区间右端点贪心，原题选最少刺点覆盖全部区间，本题选最多互不重叠区间。
56. 合并区间 中等 原题合并重叠区间保留并集，本题通过删除部分原区间消除重叠。
646. 最长数对链 中等 按结束位置判断区间重叠并进行贪心选择；本题保留尽可能多的不重叠区间，该题将数对连接视为不重叠区间选择。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/72846245
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！