3.1 区间调度算法

第三卷开篇，我们进入最优化问题——在众多候选方案里挑出"最优"的那个。这一卷有两条主线：贪心算法（3.1–3.4）和动态规划（3.5–3.9）。它们都是求解最优化问题的范式，但思路截然不同，适用边界也不同。弄清"什么时候贪心够、什么时候非得动态规划"，是这一卷最想让你带走的能力。

我们从最简单的区间调度问题入手，它是贪心算法的教科书级入门。

1.问题：选最多不冲突的活动

你有一堆活动，每个活动有开始时间和结束时间。这些活动在时间上可能冲突（有重叠），你想选出尽可能多的、互不冲突的活动参加。

形式化：给 $n$ 个区间 $[s_i, f_i)$ （ $s_i$ 开始、 $f_i$ 结束），选一个最大子集，使任意两个区间不相交。这叫区间调度（interval scheduling）问题。

朴素想法是枚举所有子集—— $2^n$ 种，爆炸。我们要高效地选出最多。

2.贪心思路：先结束的先选

贪心算法的灵魂是"每一步都做当下看起来最好的选择，不回头"。但"最好"怎么定义？这是贪心设计的关键——贪心准则选错了，整个算法就错。

区间调度有个极其聪明的贪心准则：每次选结束最早的那个活动。

直觉是：结束得越早，它占的时间窗越短，给后面留的时间越多，自然能塞进更多活动。

INTERVAL-SCHEDULE(区间集)
    按结束时间 f 升序排序
    选第一个（最早结束的）
    last_end = 它的结束时间
    依次扫描剩余区间：
        若某区间 s >= last_end（不冲突）：
            选它
            last_end = 它的结束时间
    返回选中的集合

一遍扫描， $O(n\log n)$ （排序主导）。

3.为什么这个贪心是对的：交换论证

贪心最危险的地方是"凭感觉"——感觉对的选择可能是错的。比如区间调度里，你可能想"选最长的活动"或"选最早开始的"，这两个准则都是错的（想想为什么）。所以贪心算法必须有严格证明，这一卷第四卷会专门讲证明工具，这里先用交换论证（exchange argument）给个直觉。

交换论证的核心：把任意一个最优解，一步步替换成贪心解，证明替换后不变得更差。 具体到这里：

设贪心选的第一个活动 $g_1$ （结束最早），某最优解选的第一个是 $o_1$ 。
因为 $g_1$ 结束不晚于 $o_1$ ，把最优解里的 $o_1$ 换成 $g_1$ 后，剩余可选的活动只多不少（ $g_1$ 腾出的时间窗更长）。
所以替换后仍是最优解。对后续活动重复这个论证，最终贪心解和最优解一样优。

这就证明了"最早结束优先"能得到最优。第四卷 4.5 会把交换论证做成严格的三步法。

4.贪心的两个必要条件

区间调度能贪心，是因为它满足两个条件：

贪心选择性质（greedy-choice property）。 存在一个"当下就能定的最优选择"——选最早结束的，这个选择是全局最优的一部分，不需要看后面。换句话说，局部最优选择能拼成全局最优。

最优子结构（optimal substructure）。 做了一个选择后，剩下的子问题和原问题同构（在剩余不冲突的区间里继续选最多）。这保证贪心能一路推进。

这两个条件是贪心算法能工作的根基。关键是贪心选择性质——不是所有问题都有这个性质。下一节的加权区间调度（3.5）就没有：一旦加了权重，"结束最早"就不再是最优选择（可能有个结束晚但权重超大的活动更划算），这时贪心失效，非得动态规划不可。贪心和动态规划的分水岭，就在"贪心选择性质成不成立"。

5.练习

Q1. 区间调度中，"选最早开始的活动"这个贪心准则为什么是错的？给个反例。

反例：活动 A=[1,10]（最早开始但很长）、B=[2,3]、C=[4,5]。按"最早开始"选了 A，就只能选 1 个；但最优是选 B 和 C 共 2 个。最早开始不保证结束早，可能霸占一大段时间挡住后面的活动。这正说明贪心准则必须严格证明，不能凭直觉。

Q2. 用交换论证解释：为什么"最早结束优先"能得到最优解？

任取一个最优解，其首个活动 $o_1$ 的结束时间不早于贪心首个活动 $g_1$ 。把 $o_1$ 换成 $g_1$ ：因为 $g_1$ 结束更早（或同时），剩余不冲突的活动只增不减，替换后的解仍最优。对后续活动递归重复此论证，最终贪心解与最优解等优。所以最早结束优先正确。

Q3.（思考题） 贪心算法的两个必要条件是什么？为什么说"贪心选择性质"是贪心与动态规划的分水岭？

两个条件：贪心选择性质（存在当下可定的最优选择，无需看后续）和最优子结构（做选择后剩余子问题与原问题同构）。贪心选择性质是分水岭：有它就能贪心（局部最优拼成全局最优）；没有它（如加权区间调度）则局部贪心选择会错，必须用动态规划穷举所有选择、取最优。3.5 节会直接演示这个边界。

6.小结

区间调度用"最早结束优先"的贪心准则， $O(n\log n)$ 选出最多不冲突活动。贪心靠交换论证证明正确，依赖贪心选择性质和最优子结构两个条件。记住：贪心准则选错就全错，必须严格证明。下一篇我们看贪心的另一个经典——Huffman 编码，它还要靠优先队列（1.4 的堆）来高效实现。