14.2　区间调度与 Huffman 编码

学习目标：学完本节，你能

• 说出区间调度的正确贪心策略，并用交换论证证明它（14.1 节欠的那笔账，本节还上）；
• 说清另外两个"看起来同样有道理"的策略为什么是错的；
• 实现 Huffman 编码，并解释前缀码为什么能唯一解码；
• 说清 Huffman 的"最优"到底是最优什么 —— 以及它为什么离"最优压缩"还有距离。

先修：14.1（贪心的两个前提、交换论证的模板）、11.3–11.4（优先队列）。 固定术语：贪心算法、贪心选择性质、Huffman 编码、前缀码。 环境与版本：.NET 8 / C# 12。 预计阅读：35 分钟。

一、直觉：两个问题，两种"贪心"

本节要处理两个经典问题，它们的贪心策略长得完全不像：

第二个策略尤其反直觉 —— "合并两个最小的"听起来像是在处理一棵树，和"编码"有什么关系？

这两个问题的共同点是：贪心策略都不是"显然"的，必须论证。

14.1 节欠了一笔账：讲了交换论证的四步模板，但只用它说明过"为什么贪心会错"，没真正用它证明过"贪心是对的"。本节还上。

二、区间调度：三个候选策略

问题：给你一批时间段 $[开始, 结束)$，最多能参加几个互不重叠的？

小陈的版本：一天里有一堆会议邀请，每个会议有开始和结束时间，同一时刻只能在一个会场 —— 最多能参加几个？

"每次都挑一个"的贪心，至少有三种挑法：

三种听起来都很有道理 —— 开始早的"先把时间占上"、时间短的"占得少"、结束早的"腾出时间快"。

实测结果先说结论：只有 C 是对的。

两个反例

反例 1 —— 策略 A（开始最早）：

    区间：[0,10)  [1,2)  [3,4)
    策略 A（开始最早）：选 [0,10)，后面两个都装不下 -> 1 个
    策略 C（结束最早）：选 [1,2) 再选 [3,4) -> 2 个
    暴力枚举的最优解：2 个

[0,10) 开始得最早，但它一口气占满了整段时间 —— "开始早"和"占用少"是两回事。

反例 2 —— 策略 B（时长最短）：

    区间：[0,4)  [3,7)  [5,14)  [3,6)
    策略 B（时长最短）：[3,6) 长度 3 最短，但它把另外三个全挡住了 -> 1 个
    策略 C（结束最早）：[0,4) 再选 [5,14) -> 2 个
    暴力枚举的最优解：2 个

这个反例更刁钻：[3,6) 确实是最短的那个（长度 3），但它横在正中间，把左右两边都切断了。

"占得少"和"腾出空间"也是两回事 —— [3,6) 占的是一段"关键位置"，而 [0,4) 占的是"边上"。

为什么"结束最早"就对了？ —— 因为它同时兼顾了两件事：

一个区间"结束得最早"，意味着它【剩下的可支配时间最多】。

而它占用的那段时间是不是"关键位置"，反而不重要 —— 反正任何不早于它结束的区间，都还能接在它后面。

这句话就是下一节交换论证的核心。

三、交换论证：把"结束最早"证一遍

14.1 节给的四步模板，现在完整走一遍。

命题："每次选结束时间最早的区间"，得到的区间数量一定是最多的。

第 1 步：假设存在一个最优解 $O$。

第 2 步：找到 $O$ 和贪心解 $G$ 的第一个不同。

• $O$ 的第一个区间记作 $o_1$
• $G$ 的第一个区间记作 $g_1$ —— 按策略，$g_1$ 是所有区间里结束时间最早的那个

第 3 步：证明可以把 $o_1$ 换成 $g_1$，而结果不会变差。

关键是这个不等式：

$$g_1.\text{end} \le o_1.\text{end}$$

为什么成立？ 因为 $g_1$ 是全体区间里结束最早的那个，$o_1$ 也是全体区间之一 —— 所以 $g_1$ 的结束时间不可能比 $o_1$ 晚。

现在看 $O$ 里紧接着的那个区间 $o_2$。 它必须满足：

$$o_2.\text{start} \ge o_1.\text{end}$$

（$O$ 是合法解，$o_2$ 不能和 $o_1$ 重叠）

把 $g_1$ 代进去：

$$o_2.\text{start} \ge o_1.\text{end} \ge g_1.\text{end}$$

所以 $o_2$ 和 $g_1$ 也不重叠 ✓ —— 把 $o_1$ 换成 $g_1$ 之后，$O$ 仍然是一个合法解，而且区间数量一个没少。

第 4 步：反复交换。

既然"存在一个以 $g_1$ 开头的最优解"，那就把它当作新的 $O$，对剩下的部分（$g_1$ 结束之后的所有区间）重复第 2、3 步。

每一步都把 $O$ 里的一项换成贪心的选择，而数量始终不变 —— 最后 $O$ 被改造成了 $G$，所以 $G$ 也是最优解 ✓

这个证明里，真正干的活只有一步：$g_1.\text{end} \le o_1.\text{end}$。

而这一步之所以成立，是因为"结束最早"是一个【全局】性质的判断 —— 贪心在选 $g_1$ 的时候，是拿它和所有区间比的，而不是只和"当前能选的"比。

这就是 14.1 说的「贪心选择性质」：局部最优选择（结束最早）一定属于某个全局最优解（第 4 步证明的）。

而策略 A 和 B 不满足这个性质 —— 反例里的 $[0,10)$ 和 $[3,6)$ 就是它们"局部最优但不属于任何全局最优解"的样子。

四、实测：三种策略的正确率

反例只能说明"会错"，不能说明"错得有多频繁"。 上对拍：

  随机生成 2000 组区间（每组 4~12 个，时间范围 0~20），
  每种策略都与【暴力枚举所有子集】的最优解对比：

    策略 A（开始最早）： 1251 / 2000 组正确  （62.5%）
    策略 B（时长最短）：  426 / 2000 组正确  （21.3%）
    策略 C（结束最早）： 2000 / 2000 组正确  （100.0%）

这张表要横着看，也要竖着看：

横着看：策略 C 是 100.0% —— 不是"大部分对"，是每一组都对。这正是第三节那个证明在数据上的样子。

竖着看：A 有 62.5% 正确率，B 有 21.3% —— 它们不是每次都错。

第二行值得单独看：

"每次选最短的"这个策略，在 2000 组随机数据里只有 21.3% 是对的。

但如果你随手造两个例子试了试（就像第二节那两个反例之前的随便几组），大概率会碰上"对"的那些 —— 然后你就把这个策略写进代码了。

14.1 节那句"贪心的错误是静默的"，在这里有了具体数字：78.7% 的情况下它会错，但它不会报错，只会少排几个会议。

五、Huffman 编码：合并最小的两个

换一个问题：怎么给字符设计编码，让一段文本的总比特数最少？

先看定长编码的问题

一段英文里，字母出现的次数差得非常远。本节实测样本里：

如果每个字符都用同样多的位数（比如 27 个字符用 5 位），那就等于让 z 和空格一样贵 —— 明显浪费。

变长编码的陷阱：不能随便编

自然的想法是：频繁的字符用短码，罕见的用长码。

但不能随便定。比如：

  e  -> 0
  t  -> 01      ← 有问题！

收到 01 时，它到底是"t"，还是"e 后面跟着一个 1"？ —— 有歧义，解不出来。

要能唯一解码，必须满足一个条件：

前缀码（Prefix Code）：任何一个编码，都不能是另一个编码的前缀。

上面那个例子里 0 是 01 的前缀，所以它不合法。

满足前缀码之后，解码就变得极其简单：

  从头开始读，一旦读到的 0/1 串匹配上了某个字符的编码，就切一刀，
  然后从下一个比特继续 —— 不用任何分隔符，也不会读错。

为什么会这样？ 因为没有任何一个编码是别人的前缀 —— 所以你"读到一半就停下来"的这个位置，不可能是某个更长编码的开头 ✓

这正是 Huffman 树的结构保证的：每个字符都在【叶子】上， 从根到叶子的路径是唯一的，而一条路径不可能是另一条路径的前缀。

Huffman 的策略

每次从"待合并的节点"里取出【频率最小的两个】，合成一个新节点（频率 = 两者之和），放回去。 重复到只剩一个节点为止，它就是树的根。

它为什么合理？ 一句话：

频率越低的字符，越早被合并，也就会沉到树的越深处 —— 而越深意味着编码越长。

"先把最不常用的字符埋到最深处"，就是它的贪心选择依据。

实测：构造过程

  ---------- Huffman 树的构造过程（每次合并频率最小的两个）----------
    第  1 步：合并 z(1)           和 q(2)           -> 新节点，频率 3
    第  2 步：合并 j(2)           和 内部节点(3)        -> 新节点，频率 5
    第  3 步：合并 x(3)           和 y(4)           -> 新节点，频率 7
    第  4 步：合并 内部节点(5)        和 k(5)           -> 新节点，频率 10
    第  5 步：合并 v(5)           和 c(6)           -> 新节点，频率 11
    第  6 步：合并 b(6)           和 p(6)           -> 新节点，频率 12
    第  7 步：合并 内部节点(7)        和 w(7)           -> 新节点，频率 14
    第  8 步：合并 f(7)           和 内部节点(10)       -> 新节点，频率 17
    第  9 步：合并 m(10)          和 d(11)          -> 新节点，频率 21
    第 10 步：合并 u(11)          和 内部节点(11)       -> 新节点，频率 22
    第 11 步：合并 内部节点(12)       和 g(12)          -> 新节点，频率 24
    第 12 步：合并 内部节点(14)       和 l(15)          -> 新节点，频率 29
    ...（共 26 步，最后剩一个根节点）

注意第 1 步：z（出现 1 次）和 q（出现 2 次） 是最罕见的一对，它们最先被合并，也埋得最深。

六、实测：编码表、前缀码、压缩率

编码表

      字符    频率    编码              位数
      ----    ----    ----------------    ----
      ␣         87    111                 3
      e         47    010                 3
      t         40    1101                4
      a         34    1011                4
      ...
      k          5    1100011             7
      y          4    1010001             7
      x          3    1010000             7
      j          2    11000100            8
      q          2    110001011           9
      z          1    110001010           9

看两端的对比：

差了 3 倍 —— 而这是它应该有的样子：z 出现得少，所以给它长码；空格出现得多，所以给它短码。

前缀码性质验证

  前缀码性质（没有任何一个编码是另一个的前缀）：True
    这一条是【能唯一解码】的保证 —— 收到一串 0/1 时不用分隔符就能切开。

注意编码表里的一个细节：0 开头的编码有 010、0110、0111、0001… —— 它们都以 0 开头，但没有任何一个等于 0 ✓ 这就是"前缀码"在数据上的样子。

和定长编码比

  ---------- 和定长编码比 ----------
    字母表大小 27 -> 定长编码需要 5 位/字符
    定长编码总位数：2,335
    Huffman 总位数：1,945（平均 4.165 位/字符）
    省下 16.7%

省了 16.7% —— 这个数字可能比预期的小。

很多教材讲 Huffman 时会用"压缩 50%"之类的例子 —— 那是人为构造的极端频率分布。

在真实英文文本上，Huffman 大约省 15%~25% —— 这已经不少了，但确实不是"翻天覆地"。

七、那还能再省吗？—— Huffman 的"最优"到底是最优什么

这是本节最该带走的一个认知。

先测一个数：这段文本的一元熵（信息论概念，超出本书范围，这里只用它的数值）：

  ---------- 还能再省吗？----------
    这段文本的【一元熵】是 4.117 位/字符 —— 这是「每次只看一个字符」时
    理论上不可能突破的下限（信息论，超出本书范围）。
    Huffman 做到 4.165 位/字符，与它的差距只有 0.048 位。

Huffman 用 4.165 位，理论下限是 4.117 位 —— 只差 0.048 位（约 1.2%）。

所以 Huffman 确实做到了它宣称的事：它是【最优前缀码】—— 没有任何一种"给单个字符分配变长码"的方案能比它明显更短。

但"最优前缀码"离"最优压缩"还差得远 —— 因为那个 4.117 位的下限，本身就是"每次只看一个字符"这个【模型】的下限。

要突破它，唯一的办法是换模型：

这个认知在工程里很实用：当有人告诉你"我们用 Huffman，已经是最优了"，你要问的是 —— "最优于什么模型？"

Huffman 在它自己的模型里确实是最优的，但那不等于"没法再压了"。

还有一个工程细节值得知道：Huffman 解码需要那棵码表（或者等价的频率表）。 对很小的文本，码表本身的体积可能超过省下的比特 —— 所以短文本压缩通常要另想办法（或者干脆不压）。

八、练习

练习 14.2.1（手工跑区间调度） 有四个时间段：[0,10)、[1,3)、[4,6)、[7,9)

(a) 按策略 C（结束最早）手工走一遍，写出选中的区间。 (b) 最优解是几个？请说明为什么不可能更多。 (c) 如果改成策略 A（开始最早），结果是什么？

练习 14.2.2（交换论证的细节） 回到第三节的证明：

(a) 为什么 $g_1.\text{end} \le o_1.\text{end}$ 一定成立？这个不等式的成立依赖 $g_1$ 的哪个性质？ (b) 如果把"结束最早"换成"开始最早"，第 3 步还能推出 $o_2$ 和 $g_1$ 不重叠吗？为什么？ (c) 这个证明里，哪一步用到了 14.1 节说的"贪心选择性质"？

练习 14.2.3（Huffman 的手工构造） 四个字符，频率分别是：a:40、b:20、c:15、d:5。

(a) 手工跑一遍 Huffman 构造过程，画出最终的树。 (b) 写出每个字符的编码，并算出平均编码位数。 (c) 定长编码需要几位？Huffman 省了多少？

练习 14.2.4（判断） 判断对错并说明理由： (a) Huffman 编码是压缩率最高的压缩算法。 (b) 前缀码的"前缀"指的是字符编码的前几个比特。 (c) 区间调度里，"结束最早"和"时长最短"在有的时候会选出同一个区间。 (d) 频率相同的字符，Huffman 给出的编码一定相同。

九、练习答案

14.2.1

(a) 策略 C（结束最早）

第一步：按结束时间排序：

第二步：依次挑选（要求 开始 ≥ 上一个的结束）：

结果：[1,3)、[4,6)、[7,9) —— 3 个 ✓

(b) 最优是 3 个。

为什么不可能更多？ 上面的三个区间已经把 [1,9) 这段"切"成了三块， 而 [0,10) 和它们中的任何一个都重叠 —— 四个区间里最多只能同时选 3 个 ✓

(c) 策略 A（开始最早）：只选出 1 个。

按开始时间排序：[0,10)(0)、[1,3)(1)、[4,6)(4)、[7,9)(7)

结果：只有 [0,10) —— 1 个。

这就是第二节反例 1 的形状：[0,10) 开始最早，但它结束得最晚 —— "开始早"和"结束早"是两件完全不同的事，而区间调度要的是后者。

14.2.2

(a) 因为 $g_1$ 是【全体区间里】结束最早的那个。

这正是"贪心选择"的定义 —— 它不是"当前能选的里面结束最早的"，而是所有区间里结束最早的。

所以对任何其他区间 $o_1$（包括最优解的第一个），都有 $g_1.\text{end} \le o_1.\text{end}$ ✓

注意这个性质的强度："全局最早"比"局部最早"强得多 —— 正因为如此，$g_1$ 才能无条件地换进任何最优解。

(b) 不能。

如果是"开始最早"，我们只能保证：

$$g_1.\text{start} \le o_1.\text{start}$$

但我们需要的是 $o_2.\text{start} \ge g_1.\text{end}$ —— 而"开始早"对"结束"没有任何约束。

反例就是第二节那个：g_1 = [0,10) 开始最早，但它的结束时间 10 把 [1,2) 和 [3,4) 全挡住了。

一句话："开始早"约束的是区间的【左端点】，而"不重叠"看的是【右端点】。

要保证留给后面的空间尽可能大，必须看右端点 —— 这就是"结束最早"胜出的原因。

(c) 在第 3 步。

第 3 步证明的是："结束最早"这个局部选择，可以放进某个全局最优解里 —— 这恰好就是"贪心选择性质"的定义。

而第 4 步只是把这个论证重复应用到剩余部分 —— 那是"最优子结构"在起作用（14.1 节说过，DP 也需要它）。

所以这个证明的结构是： 贪心选择性质（第 3 步）+ 最优子结构（第 4 步）→ 贪心正确 —— 正是 14.1 节那两个前提。

14.2.3

频率：a:40、b:20、c:15、d:5

(a) 构造过程

第 1 步：取最小的两个 —— d(5) 和 c(15) → 合并成 X(20) 第 2 步：现在有 a(40)、b(20)、X(20)。取最小的两个 —— b(20) 和 X(20) → 合并成 Y(40) 第 3 步：现在有 a(40)、Y(40)。合并 → 根节点 Z(80)

                    Z(80)
                   /     \
               a(40)      Y(40)
                         /     \
                    b(20)       X(20)
                               /     \
                           d(5)       c(15)

注意第 2 步有个"平局"：b(20) 和 X(20) 频率相同，先合并哪个都行 —— 这会得到结构不同但总长度相同的树（见小题 (d) 的辨析）。

(b) 编码与平均位数

平均位数：

$$\frac{40 \times 1 + 20 \times 2 + 5 \times 3 + 15 \times 3}{80} = \frac{40 + 40 + 15 + 45}{80} = \frac{140}{80} = 1.75 \text{ 位}$$

(c) 定长编码需要 2 位（4 个字符，$\lceil \log_2 4 \rceil = 2$）。

Huffman 平均 1.75 位，省下：

$$\frac{2 - 1.75}{2} = 12.5\%$$

注意这个压缩率比本节正文里的 16.7% 更低 —— 因为这里只有 4 个字符，频率分布也不够极端。

Huffman 的收益取决于"频率有多不均匀"：越不均匀，省得越多。 如果四个字符频率都是 25，Huffman 会给出全 2 位的编码，一点都省不了。

14.2.4

(d) 这一条有个实际影响：Huffman 编码不是唯一的。

所以解码方必须拿到发送方的码表（或者用完全相同的构建规则 + 相同的平局打破策略）—— 这就是上一节末尾提到的"码表开销"问题的根源。

十、常见错误

十一、本节总结

1. 区间调度的正确贪心：每次选结束时间最早的。 另外两个策略（开始最早、时长最短）都错。
2. 交换论证完整走了一遍：核心只有一步 —— $g_1.\text{end} \le o_1.\text{end}$（因为 $g_1$ 是全局结束最早的）， 所以把最优解的第一项换成 $g_1$，后面的区间照样不重叠，反复交换即得贪心解也是最优 ✓
3. 为什么"结束最早"胜出："开始早"约束的是左端点，而"不重叠"看的是右端点。
4. 实测：三种策略正确率 62.5% / 21.3% / 100.0%。 A 和 B 不是每次都错 —— 这正是静默错误的可怕之处。
5. Huffman 编码：每次合并频率最小的两个，让罕见的字符沉到树的最深处。
6. 前缀码：没有任何编码是另一个的前缀 —— 这是"不用分隔符就能唯一解码"的保证，也是 Huffman 树"字符都在叶子上"的直接推论。
7. 实测：真实英文样本上省 16.7%（定长 5 位 → Huffman 4.165 位），比教材例子朴素得多。
8. Huffman 的最优是最优【前缀码】：实测 4.165 位 vs 一元熵 4.117 位，只差 0.048 位 —— 但那意味着"在这个模型里已经到顶了"，要更省必须换模型。

下一节衔接：本节的两个贪心都证对了 —— 区间调度走了完整的交换论证，Huffman 给了直觉依据。

但贪心不是总能证的。 14.1 节已经看过一次失败（找零），14.3 节会看到更经典的一次：

同一个背包问题，只差一个条件（"物品能不能切分"），贪心从"完美正确"变成"错得离谱"。

而且 14.3 会回答一个更实用的问题：我怎么知道该收手了、该换动态规划了？

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "14.2",
  "title": "区间调度与 Huffman 编码",
  "covered": [
    "区间调度的三个候选贪心策略（开始最早 / 时长最短 / 结束最早）",
    "两个反例：策略 A 被「开始早但特别长」击破，策略 B 被「短但横在中间」击破",
    "交换论证的完整四步演练（14.1 节欠的账）",
    "「结束最早」胜出的根本原因：不重叠看的是右端点",
    "实测：三种策略在 2000 组随机数据上的正确率 62.5% / 21.3% / 100.0%",
    "定长编码的浪费与变长编码的歧义问题",
    "前缀码的定义、唯一解码的原理、与 Huffman 树「字符在叶子上」的对应",
    "Huffman 的构造过程逐步骤追踪（26 步合并）",
    "编码表实测（空格 3 位 vs z 9 位）、前缀码性质验证",
    "压缩率实测：定长 5 位 → Huffman 4.165 位，省 16.7%",
    "Huffman 最优性的边界：4.165 位 vs 一元熵 4.117 位，只差 0.048 位",
    "「最优前缀码 ≠ 最优压缩」：要更省必须换模型"
  ],
  "unresolved": [
    "Huffman 最优性的严格证明（比区间调度复杂）未展开",
    "信息论中的熵只取数值使用，概念本身超出本书范围",
    "算术编码、LZ 系列等更强的压缩方法超出本书范围",
    "贪心失效的反例留到 14.3"
  ],
  "canonical_terms": {
    "Huffman 编码（Huffman Coding）": "每次合并频率最小的两个节点来构造编码树，得到最优前缀码",
    "前缀码（Prefix Code）": "没有任何一个编码是另一个编码前缀的编码方案，可无分隔符唯一解码",
    "区间调度（Interval Scheduling）": "在互不重叠的前提下选出最多区间的问题；贪心策略是每次选结束最早的"
  },
  "symbols_units": {
    "g1 / o1": "贪心解 / 最优解的第一个区间",
    "n": "区间个数"
  },
  "assumptions": [
    "读者已掌握 14.1 的交换论证模板与两个前提",
    "读者理解 11.3 的优先队列（Huffman 用它取最小两个）",
    "区间采用半开形式 [开始, 结束)，不重叠的判据是 下一个.开始 >= 上一个.结束"
  ],
  "word_count_actual": 3835,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑（AMD Ryzen 7 9700X），输出见正文",
    "项目文件：99-tools/samples/Ch14/Sec142/",
    "实验一：两个反例（开始最早、时长最短各一）为实测",
    "实验一：2000 组随机区间（seed=20260918，每组 4~12 个，时间范围 0~20）对拍暴力枚举，正确率 1251/426/2000 为实测",
    "实验二：Huffman 构造 26 步、编码表、前缀码 True、定长 2335 位 vs Huffman 1945 位（16.7%）、一元熵 4.117 位均为实测",
    "术语写法与 glossary.md 一致（贪心算法、贪心选择性质、Huffman 编码、前缀码）"
  ],
  "known_issues": [
    "实验一初版设计反例 2 时反复失败：随手构造的「短区间」例子往往让「时长最短」也选出正确解 —— 最后用「一个短区间横在中间、两侧各有一个长区间」的形状才做出反例（[0,4) [3,7) [5,14) [3,6)）",
    "练习 14.2.1 初版用 [1,3) [2,5) [4,6) [5,8) [7,9)，但那个例子里策略 A 和策略 C 结果相同，小题 (c) 失去意义 —— 改为 [0,10) [1,3) [4,6) [7,9)，让 A 只能选出 1 个（对照 C 的 3 个）",
    "verbose 的步数打印初版把「超出 12 步」的省略提示写在了 while 循环体内，会重复打印 —— 移到循环外",
    "注释里残留了从 14.1 复制过来的「coins 式的统一写法」字样，已改为描述区间调度的正确表述"
  ],
  "next": "14.3 贪心失效的反例"
}