数据结构与算法 / 系统课时

用区间贪心安排不冲突选择

用区间贪心安排不冲突选择

区间题常把目标包装成会议安排、删除重叠区间或射气球,但核心决策经常相同:如何给后续选择留下尽可能大的空间。本篇从“优先选择结束最早的区间”出发,推导不重叠区间的标准贪心,并说明何时应按右端点排序。

学习目标

  • 能把删除重叠区间转化为最大化不冲突区间数量
  • 掌握按结束位置排序并线性扫描的区间贪心
  • 能用交换论证解释为什么结束最早的可行区间安全

把删除问题改写成选择问题

以 LeetCode 435“无重叠区间”为例,要求删除最少的区间,使剩余区间互不重叠。直接思考“每次删哪个”会产生很多分支,更简单的等价目标是:尽量保留更多互不重叠的区间。

如果总共有 n 个区间,最多能保留 k 个不重叠区间,那么最少删除数就是 n - k。问题由删除决策变成经典区间选择。

关键规则是按右端点从小到大排序。每次遇到与已选区间不冲突的区间就接受它,并把当前结束位置更新为该区间的右端点。

结束最早区间为后续选择保留更大空间

为什么要按右端点排序

假设当前所有可行区间中,贪心选择结束最早的区间 G;某个最优方案第一项却选择了结束更晚的 O。因为 G 的结束时间不晚于 O,把最优方案中的 O 替换成 G 后,原本能排在 O 后面的区间依然能够排在 G 后面。

因此这次交换不会减少后续可选区间数量,也不会降低最终保留数量。于是至少存在一个最优方案以 G 开头,贪心选择是安全的。固定 G 后,对右侧剩余区间继续应用同样规则即可。

这也解释了为什么通常不是按开始时间最早排序。开始得早并不代表释放资源早;一个很早开始但持续很久的区间,反而可能挡住大量短区间。

实现不重叠区间选择

下面直接求最少删除数。排序后只需要维护最后一个已保留区间的结束位置,时间复杂度主要来自排序。

python
from typing import List


def erase_overlap_intervals(intervals: List[List[int]]) -> int:
    if not intervals:
        return 0

    intervals.sort(key=lambda interval: interval[1])
    kept = 0
    end = float("-inf")

    # 只接受起点不早于当前结束位置的区间。
    for start, finish in intervals:
        if start >= end:
            kept += 1
            end = finish

    return len(intervals) - kept


if __name__ == "__main__":
    data = [[1, 2], [2, 3], [3, 4], [1, 3]]
    print(erase_overlap_intervals(data))

预期输出

text
1

可以保留 [1, 2]、[2, 3]、[3, 4] 三个区间,只需删除 [1, 3]。这里把端点相接视为不重叠,因此判断条件使用 start >= end;如果题目把接触端点也定义为冲突,就要按题意修改边界条件。

区间题先判断目标再排序

“区间题就按右端点排序”同样不是万能公式。排序依据来自目标,而不是数据长得像区间。

当目标是选择最多互不重叠区间、删除最少重叠区间时,结束最早通常是关键,因为它最大化后续剩余空间。LeetCode 452“用最少数量的箭引爆气球”也可以围绕右端点决策:在当前公共可射范围的右侧尽量晚地放箭,从而争取让一支箭覆盖更多后续气球。

而“合并区间”解决的是把所有覆盖范围归并,并不是从候选区间中做舍弃选择。它通常按左端点排序,然后持续扩展当前合并区间的右边界。两类题都需要排序扫描,但贪心变量和证明目标不同。

复杂度与边界

设区间数量为 n。排序需要 O(n log n),随后扫描一次需要 O(n);除排序实现使用的额外空间外,贪心状态只保存计数和一个结束位置。

空输入应返回 0。端点能否相等、区间是闭区间还是半开区间,则必须以题目定义为准。真正需要记住的不是某一行比较符号,而是“用最早释放资源的选择,为后续保留最大可行空间”这一决策原则。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用区间贪心安排不冲突选择

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通