专题进阶 · 贪心策略推荐总顺序 · 第 81 / 148 课

用最早结束时间最大化不重叠区间数量,识别加权版本的变化。

先学会这些,再进入本课 贪心思想 区间合并
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 贪心策略

区间贪心Interval Greedy

最大不重叠区间数量可按结束时间选取;换成收益最大后通常需要 DP。

建议 40 分钟 · 含手算、代码与三层练习

本课要建立的能力

用最早结束时间最大化不重叠区间数量,识别加权版本的变化。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

有活动 [1,4)、[2,3)、[3,5)、[5,7),只能参加互不重叠活动,最多选几个?

02一步步得到方法

为什么选最早结束,而不是最早开始

越早结束给后续留下的时间不比其他首活动少。若最优方案第一个活动为 B,而 A 是最早结束活动,把 B 换成 A,之后原来能接 B 的活动也一定能接 A,活动数不变。

确定 A 后,剩下只需在开始时间≥A.end 的活动里解决同样问题,因此可重复应用这条安全规则。这既有贪心选择性质,也有剩余子问题结构。

输入语义与目标要固定

本课活动为半开区间 [start,end),end 相同于下一活动 start 可接续,且每活动收益都算 1。若要最大总收益,最早结束可能丢掉一个很高收益的长活动,通常改用带前驱查找的加权区间 DP。

结束早保留更多未来空间

在最大化互不冲突活动数量的问题中,把最优解第一项替换成结束更早的可选活动,不会减少它后面能接的活动。重复这个交换就得到按结束时间选择的正确性。

如果每项活动价值不同,结束早只保证留下时间,不保证留下更高价值组合;这时可能需要按结束排序后的加权区间 DP。目标从数量变为收益是一个真正的算法变化。

03把一个小例子完全算清楚

活动 [1,4)、[2,3)、[3,5)、[5,7)。

步骤计算与状态为什么这样做
按结束排序[2,3)、[1,4)、[3,5)、[5,7)结束越早越先考虑
选 [2,3)last_end=3给后续留空间
跳 [1,4),选 [3,5)last_end=5允许首尾相接
选 [5,7)共 3 个最优

窄屏可左右滑动表格,阅读完整计算与理由。

按最早开始会先选 [1,4),本例只能再接 [5,7),少选一个。

04为什么这个方法成立

  1. 将任意最优方案首活动替换为最早结束活动,不减少后续可行集合。
  2. 剩余活动构成同类型问题。
  3. 递归地安全固定首项,最终获得最大数量。

05把推导翻译成代码

Python · 可独立运行的教学实现

def choose_intervals(intervals):
    chosen, end = [], float("-inf")
    for start,finish in sorted(intervals,key=lambda x:x[1]):
        assert start < finish
        if start >= end:
            chosen.append((start,finish))
            end = finish
    return chosen

逐个理解关键决定

key=lambda x:x[1]
按结束时间排序,目标不是最大覆盖长度。
start >= end
半开区间相接合法;闭区间不重叠要求可能是严格大于。

06时间、空间与实现范围

排序 O(n log n),扫描 O(n),输出与排序副本 O(n)。

允许零长度活动时需额外定义是否占用时间和同坐标顺序;本实现要求正长度。

07改变条件,检查哪里会出错

按区间最短排序

最短活动可能卡在中间,同时阻塞两侧可连续活动;没有最早结束的交换保证。

把加权收益问题当成数量问题

例如一个长活动价值很高时,选最多短活动不一定利润最高。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

[1,10) 与 [2,3)、[3,4)、[4,5) 选什么?

需要一点提示

比较数量而非时长。

查看解析与答案

后三个,共 3 个。

练习 2 · 边界与辨析

若 [1,10) 收益 100,其余各 1 呢?

需要一点提示

目标函数变了。

查看解析与答案

应选收益 100,原贪心不适用,需加权调度算法。

练习 3 · 变式与迁移

如何求最少删除多少区间使不重叠?

需要一点提示

保留数量最大。

查看解析与答案

原数量减去最大可选数量,在同一端点语义下成立。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

MIT 6.006 · 算法讲义

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。