exchange argument

交换论证：贪心凭什么最优

一批活动申请同一间实验室，每份申请给出开始与结束时刻，时间重叠的两份不能同时批准，目标是批准的份数最多。这道题的贪心解法只有一句话：按结束时刻从早到晚看，不与已选冲突就选。按开始时刻看、按时长从短到长看、按冲突数从少到多看，写起来一样自然，正确性却都不成立。本页处理的就是这个落差：区分对错的不是代码，是一套可以逐步执行的论证。

同一批区间还有另一个问题——把全部区间分进最少的房间，那道题的贪心走的是开始时刻序，见区间图：贪心直接最优。两道题共用一批数据，选取规则却不同，这一点本身就说明「按什么排序」不是可以随手定的细节。

1 · 问题与候选规则

**定义 1.1（interval scheduling）**给定 $n$ 个区间 $[s_i, f_i)$ ，若两个区间的交为空则称它们相容。求一个两两相容的子集，使其中区间的个数最多。

四条规则都能写成同一个循环：从候选集里取出打分最小的一个放进解，把与它相交的候选全部删掉，重复到候选集空。差别只在打分函数：

earliest finish time 取 $f_i$ ；
earliest start time 取 $s_i$ ；
shortest interval 取 $f_i - s_i$ ；
fewest conflicts 取「当前候选集里与它相交的个数」。

前三条的打分与候选集无关，可以一次排序定序；第四条的分值随候选集缩小而变化，每轮都要重算。

图 1-1 · 四条选取规则在四组区间上的逐轮执行。可切换实例与规则，对照下方的贪心解大小与最优解大小的差值。

本页主实例有 11 个区间、最优解 5 个。四条规则在它上面选出的是同一组区间 $A, D, G, J, L$ ，连大小都不必比较。fewest conflicts 的挑选次序是从右往左的（ $L, J, G, A, D$ ），走法完全不同，结果却一致。这说明反例不会在随手写的数据上自己冒出来：三个反例都得照着论证的断裂处倒推着造。

2 · 交换论证的模板

定理 2.1earliest finish time 规则给出的相容子集，个数等于最优解的个数。

证明设贪心解为 $G = g_1, \dots, g_k$ ，取任一最优解 $O = o_1, \dots, o_m$ ，两者都按结束时刻递增排列。

若 $G$ 与 $O$ 逐位相同，结论已成立。否则设第一处分歧在第 $r$ 位，即 $g_j = o_j$ 对一切 $j < r$ 成立而 $g_r \ne o_r$ 。

$o_r$ 与前缀 $o_1, \dots, o_{r-1} = g_1, \dots, g_{r-1}$ 相容，说明贪心在第 $r$ 轮时 $o_r$ 仍在候选集里；而贪心取的是候选集中结束最早的那个，故 $f(g_r) \le f(o_r)$ 。

把 $O$ 的第 $r$ 项换成 $g_r$ 。换后仍两两相容： $g_r$ 与前缀相容是贪心的选取条件， $g_r$ 与 $o_{r+1}, \dots, o_m$ 相容则由 $f(g_r) \le f(o_r) \le s(o_{r+1})$ 得到。个数没变，所以换出来的仍是最优解，且与 $G$ 的公共前缀长了一位。

公共前缀的长度每轮严格增加、又不超过 $\min(k, m)$ ，有限步后 $O$ 的前 $k$ 项与 $G$ 逐位相同。此时 $O$ 若还有第 $k+1$ 项，它与 $G$ 的全部成员相容，贪心的候选集在结束时就不会是空的，矛盾。故 $m = k$ 。∎

论证里被反复使用的只有一句： $f(g_r) \le f(o_r)$ 。它不是区间调度的性质，是 earliest finish time 这条规则的性质。换一条规则，这一句立刻失去依据，而证明的其余部分原封不动。

3 · 从最优解到贪心解的改造

上面的证明是一个可以真跑的过程：给定一个最优解，反复找第一处分歧并就地改写，直到它与贪心解逐位相同。主实例的最优解恰好有三个，改造它们分别需要 0、1、2 次交换： $A, D, G, J, L$ 就是贪心解本身； $A, E, G, J, L$ 在第 2 位换一次； $B, E, G, J, L$ 先在第 1 位把 $B$ 换成 $A$ ，再在第 2 位把 $E$ 换成 $D$ 。

图 3-1 · 交换论证的逐步执行：每一步把当前最优解的第一处分歧改写成贪心的选择。可切换贪心规则与起手的最优解，观察论证在哪一位断裂。

改造过程只承认两件事：换进来的区间仍与其余部分相容，以及个数不变。哪一件不成立，论证就停在那一位上，页面把停下的位置与被压掉的区间一并标出来。

4 · 反例的构造

三条落选的规则各有一个最小的反例，都能在图 1-1 里切换过去跑完。

规则	反例区间	贪心	最优
earliest start time	$[0,10)$ 、 $[1,3)$ 、 $[4,6)$ 、 $[7,9)$	1	3
shortest interval	$[0,4)$ 、 $[3,5)$ 、 $[4,8)$	1	2
fewest conflicts	见下	3	4

前两个反例的构造思路一样：让规则偏爱的那个区间横跨在其余区间之上。开始最早的那个是横跨全程的 $[0,10)$ ，它一进解就压掉另外三个；最短的 $[3,5)$ 只有 2 个单位长，却正好骑在 $[0,4)$ 与 $[4,8)$ 的接缝上。

fewest conflicts 的反例要绕一层。骨架是四个互不相交的区间 $A = [0,4)$ 、 $B = [8,12)$ 、 $C = [16,20)$ 、 $D = [24,28)$ ，它们构成唯一的最优解。再加一个 $E = [10,17)$ ，它只与 $B$ 、 $C$ 相交，冲突数为 2。其余六个区间的作用是把骨架四项的冲突数垫到 3 以上： $[2,10)$ 、 $[2,9)$ 、 $[3,10)$ 三个互相重叠并同时压住 $A$ 与 $B$ ， $[18,26)$ 、 $[19,26)$ 、 $[18,25)$ 三个对 $C$ 与 $D$ 做同样的事。于是全场冲突最少的是 $E$ ，而选中 $E$ 等于一次砍掉最优解的中段两项。

警示 ·「冲突少」是关于当前候选集的量，不是关于最终解的量。 $E$ 的两个冲突各值一项最优解成员，而 $A$ 的三个冲突彼此重叠、总共只挡住一项。冲突数没有区分这两种情形的能力。

5 · 论证的断裂位置

三条规则断在同一句话上，但断法不同。earliest start time 与 shortest interval 在第 1 位就断：换进来的区间结束得比 $o_1$ 晚，与最优解的后续成员相交，交换直接把解变小。fewest conflicts 的第一位反而对得上。它先选的是 $E$ ，但按结束时刻重排后排在最前的是 $A$ ，与最优解的第 1 项一致；断裂发生在第 2 位， $E$ 的结束时刻 17 晚于 $B$ 的 12，换进来会压掉 $C$ 。

这个差别值得记住：公共前缀能对上几位，与规则的对错无关。前缀长只说明反例构造得更精细，不说明论证更接近成立。

还有一处与直觉相反。fewest conflicts 在主实例上给出的解与 earliest finish time 完全相同，逐个区间都一样；写这一页时先用主实例验四条规则，四条全绿，反例是回过头照着 $f(g_r) \le f(o_r)$ 这一句倒推出来的。测试里锁住的正是这个事实，它比任何一句「贪心不一定对」都更说明问题：一条错误的规则可以在一批不算小的数据上一次都不出错。

区间带上权重后，earliest finish time 立刻失效——权重最大的单个区间可能抵得过好几个短区间，而交换论证要求的「个数不变」变成了「权重不减」， $f(g_r) \le f(o_r)$ 不再蕴含这一点。带权版本的标准解法是按结束时刻排序后做一维递推，属于动态规划的范畴；本系列的下一页从另一侧说明同一件事：两两不交的区间集不构成 matroid。

同一套模板还撑着别的贪心。Huffman 建树的正确性论证也是取一个最优前缀码、找到它与 Huffman 树的分歧、交换两个叶子并验证代价不增；Kruskal 的 cut theorem 则是把交换换成了「割上最小的横跨边可以替换任一横跨边」。模板不变，变的是「不会变差」那一步靠什么撑住。

6 · 参考文献

Kleinberg, J., & Tardos, É. (2005). Algorithm design (§4.1). Addison-Wesley.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms (3rd ed., ch. 16). MIT Press.
Gavril, F. (1972). Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM Journal on Computing, 1(2), 180–187.