3.5 加权区间调度

这一篇是贪心与动态规划的分水岭。问题几乎和 3.1 的区间调度一样——选互不冲突的区间——只多了一个东西：每个区间有权重（价值）。目标是让所选区间的权重之和最大，而不是选最多。

就这一个"加权"，让 3.1 的贪心准则彻底失效，逼出了动态规划（Dynamic Programming，DP）。它是 DP 的教科书级入门，也是理解"什么时候贪心够、什么时候非得 DP"的最佳教具。

1.问题与贪心的失效

给 $n$ 个区间 $[s_i,f_i)$ ，每个有权重 $v_i$ 。选互不冲突的子集，使权重和最大。

3.1 的贪心准则是"最早结束优先"，它优化的是"选最多"。现在加了权重，"最多"不再等于"最优"——可能选 1 个权重超大的活动，比选 3 个小权重的更划算。"最早结束优先"会贪心地选那个结束早但权重小的，错过结束晚但权重大的，贪心选择性质被破坏了。

试着换个贪心准则？"单位时间权重最大优先"？也能构造反例推翻。这个问题的贪心选择性质根本不成立——任何"当下定死"的选择都可能因权重而错。必须穷举所有"选/不选"的选择，动态规划登场。

2.动态规划的两步：定义状态、写递推

动态规划的灵魂是把问题拆成子问题，用子问题的解拼出原问题的解。关键两步：

第一步·定义状态。 把区间按结束时间排序，设 $\text{OPT}(j)$ = 考虑前 $j$ 个区间时能获得的最大权重。这是"子问题"——前 $j$ 个 vs 前 $n$ 个。

第二步·写递推（状态转移）。 对第 $j$ 个区间，我们只有两种选择：

不选它：最大权重 = $\text{OPT}(j-1)$ （前 $j-1$ 个的最优）。
选它：那和它冲突的都不能选。设 $p(j)$ 是"结束时间不晚于第 $j$ 个开始时间、且下标最大的那个区间"（即选了 $j$ 还能兼容的最近一个）。权重 = $v_j + \text{OPT}(p(j))$ 。

取两者较大：

\text{OPT}(j)=\max\Big(\text{OPT}(j-1),\ v_j+\text{OPT}(p(j))\Big)

这就是状态转移方程。基底 $\text{OPT}(0)=0$ 。

$p(j)$ 可以预先对每个 $j$ 用二分（1.3）算出来（在按结束排序的区间里二分找最后一个结束 $\le s_j$ 的）， $O(n\log n)$ 预处理。

3.从递推到算法：自底向上填表

有了递推，按 $j=1,2,\dots,n$ 顺序填一张表 $\text{OPT}[0..n]$ ，每个值依赖更小的下标，所以自底向上能填完：

WEIGHTED-INTERVAL-SCHEDULING
    按结束时间排序区间
    预处理 p(j)：对每个 j，二分找最大的 i 使 f_i <= s_j
    OPT[0] = 0
    for j = 1 to n:
        OPT[j] = max(OPT[j-1], v[j] + OPT[p(j)])
    return OPT[n]

填表 $O(n)$ ，预处理 $O(n\log n)$ ，总共 $O(n\log n)$ 。要还原"选了哪些"（而不只是最大权重），再记一张决策表回溯即可。

4.动态规划的两个前提

加权区间调度能 DP，是因为它满足 DP 的两个前提（和贪心的两个前提对照看）：

最优子结构。 $\text{OPT}(j)$ 的最优解，由子问题 $\text{OPT}(j-1)$ 或 $\text{OPT}(p(j))$ 的最优解拼成——子问题的最优能组合成原问题的最优。这点贪心也需要，两者都要求。

重叠子问题。 不同的 $\text{OPT}(j)$ 会反复用到相同的更小子问题（比如 $\text{OPT}(p(j))$ 可能被多个 $j$ 引用）。DP 用"填表缓存"避免重复计算，这是它相对朴素递归的优势。

贪心 vs DP 的真正分水岭是"贪心选择性质"：

有贪心选择性质 → 能当下定最优选择 → 贪心够（3.1 区间调度）。
没有贪心选择性质 → 当下定不了，得穷举选/不选 → 必须 DP（加权区间调度）。

两者都要最优子结构，差别就在贪心选择性质成不成立。判断一个优化问题该用贪心还是 DP，先问："我能当下就定一个最优选择吗？"能就贪心，不能就 DP。 这是这一卷最核心的判据。

5.对照 3.1：同一问题，两套范式

把 3.1 和 3.5 摆一起，分水岭一目了然：

	3.1 区间调度	3.5 加权区间调度
目标	选最多个	选权重和最大
贪心选择性质	✓（最早结束即最优一部分）	✗（权重让"最早结束"可能错）
解法	贪心 $O(n\log n)$	动态规划 $O(n\log n)$
复杂度	同阶，但 DP 要填表、更"重"

就多了"权重"一个维度，范式就变了。这种"同一问题、加个维度、范式切换"的现象，在算法设计里很常见，值得你建立这个敏感度。

6.练习

Q1. 为什么 3.1 区间调度能贪心，而 3.5 加权区间调度必须动态规划？关键差别在哪？

关键是贪心选择性质。3.1（选最多，无权重）有贪心选择性质：最早结束的活动一定是某个最优解的一部分，当下可定。3.5 加了权重后，"最早结束"可能权重极小，选它不如选个结束晚但权重大的——当下定不了最优选择，贪心选择性质失效，必须用 DP 穷举选/不选。差别就在这一个"权重"维度，破坏了贪心选择性质。

Q2. 写出加权区间调度的状态转移方程，解释 $\text{OPT}(j)$ 和 $p(j)$ 各是什么。

$\text{OPT}(j)$ = 前 $j$ 个区间（按结束排序）能获得的最大权重和。 $p(j)$ = 下标最大的、结束时间 $\le s_j$ 的区间（选了 $j$ 还能兼容的最近一个）。转移： $\text{OPT}(j)=\max(\text{OPT}(j-1),\ v_j+\text{OPT}(p(j)))$ ——不选 $j$ 取前者，选 $j$ 取后者（加上与 $j$ 兼容的前缀的最优）。

Q3.（思考题） 动态规划和贪心都需要"最优子结构"，那它们的真正分水岭是什么？给一个判据。

分水岭是贪心选择性质：能不能"当下就定一个最优选择，无需看后续"。能定 → 贪心（局部最优拼全局最优）；不能定、必须穷举所有选择 → DP。两者都要最优子结构（子问题最优能拼成原问题最优），但只有贪心还额外要求贪心选择性质。判据：问自己"这个问题里，我能不能不看后面就确定当前的最优选择？"能就贪心，不能就 DP。

加权区间调度因多了"权重"，破坏了贪心选择性质，逼出动态规划。DP 两步：定义状态 $\text{OPT}(j)$ 、写转移方程 $\max(\text{OPT}(j-1), v_j+\text{OPT}(p(j)))$ ，自底向上填表 $O(n\log n)$ 。贪心与 DP 的分水岭是贪心选择性质，两者都要最优子结构。下一篇我们继续 DP，看矩阵链乘法——它展示了 DP 的另一种典型结构（区间 DP）。