14.1 贪心算法

前置：经典动态规划与排序。本页从活动选择的交换论证出发，再用加权区间调度展示反例，并实现边界完整的 Huffman 编码。

上一章的 DP 保留多个候选状态。贪心算法更果断：每一步只做一个选择，不再回头。代码通常更短，正确性条件却更苛刻。不能因为某个局部规则“看起来合理”就采用它，必须证明至少存在一个最优解包含该选择，并且选择后的剩余部分仍是同类子问题。

活动选择：最早结束的优先

目标是选择尽量多的互不重叠活动。采用半开区间 [start, end)，允许前一个结束时立刻开始下一个；本例要求整数端点且 start < end，不处理零时长活动。

def activity_selection(activities):
    activities = list(activities)
    for start, end in activities:
        if not isinstance(start, int) or not isinstance(end, int) or start >= end:
            raise ValueError("activities require integer start < end")
    ordered = sorted(activities, key=lambda item: item[1])
    selected = []
    last_end = None
    for start, end in ordered:
        if last_end is None or start >= last_end:
            selected.append((start, end))
            last_end = end
    return selected

activities = [(540, 630), (570, 660), (630, 690),
              (660, 720), (690, 750), (720, 780)]
assert activity_selection(activities) == [
    (540, 630), (630, 690), (690, 750)
]
assert activity_selection([]) == []

时间用午夜后的分钟数表示，避免用 10.5 这种浮点数混淆“十点半”和格式化输出。函数复制并排序输入，不改变调用者的列表。排序是 O(n log n)，之后扫描 O(n)；输入副本与输出合计 O(n) 空间。整数时间也可以相对其他起点计数，不限于一天。

设 g 是最早结束的活动，某个最优解先选 o。因为 g 的结束时间不晚于 o，用 g 替换 o 不会挡住原先排在 o 之后的活动，数量也不变。于是存在一个包含 g 的最优解；去掉 g 后，对剩余兼容活动重复这个论证。这就是本题的贪心选择证明。

DP vs 贪心

维度	动态规划	贪心
保留信息	同时比较多个子状态	只保留已证明安全的当前选择
正确性核心	状态覆盖全部合法方案，转移无遗漏	交换论证、领先性质或问题专用证明
复杂度	取决于状态数与转移成本	取决于排序、堆和扫描等实现
失败信号	状态遗漏或计算顺序错误	局部选择无法交换进某个最优解

加权区间调度：贪心失灵

每个活动权重不同时，“最早结束优先”可能失灵：一个高权重活动可能比多个低权重活动更值钱。以下例子按结束时间贪心只能得到权重 4，DP 则得到 100。

def weighted_interval_scheduling(intervals):
    intervals = list(intervals)
    for start, end, weight in intervals:
        if any(not isinstance(value, int) for value in (start, end, weight)):
            raise ValueError("interval fields must be integers")
        if start >= end:
            raise ValueError("interval start must be less than end")
    intervals.sort(key=lambda x: x[1])
    n = len(intervals)
    dp = [0] * (n + 1)
    p = [0] * n
    for i in range(n):
        lo, hi = 0, i - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if intervals[mid][1] <= intervals[i][0]:
                lo = mid + 1
            else:
                hi = mid - 1
        p[i] = hi + 1
    for i in range(1, n + 1):
        dp[i] = max(dp[i - 1], intervals[i-1][2] + dp[p[i-1]])
    return dp[n]

print(weighted_interval_scheduling([(0,2,2),(1,3,100),(2,4,2)]))
# 预期: 100（选中间的高权重区间）

函数复制输入后排序，要求三个字段为整数且 start < end；允许负权重，也允许一个活动都不选，空输入返回 0。dp[i] 表示排序后前 i 个活动的最优总权重，p[i] 是第 i 个活动之前、结束时间不超过其开始时间的活动个数。选择当前活动时读取 dp[p[i]]，不选则沿用前缀答案。排序和 n 次二分共 O(n log n) 时间，额外空间 O(n)，函数只返回权重。

---

哈夫曼编码：数据压缩的贪心

给一串字符，每个有出现频率。为每个字符设计一个二进制前缀码，使频率乘码长的总和最小；“前缀码”要求没有码字是另一码字的前缀，才能连续解码。策略是每次合并频率最小的两个节点。

import heapq
from collections import Counter
from itertools import count

def huffman_codes(text):
    if not isinstance(text, str):
        raise TypeError("text must be a string")
    if not text:
        return {}

    sequence = count()
    heap = [
        (frequency, next(sequence), character)
        for character, frequency in Counter(text).items()
    ]
    heapq.heapify(heap)

    while len(heap) > 1:
        left_frequency, _, left = heapq.heappop(heap)
        right_frequency, _, right = heapq.heappop(heap)
        parent = (left, right)
        heapq.heappush(
            heap,
            (left_frequency + right_frequency, next(sequence), parent),
        )

    codes = {}

    def visit(node, prefix):
        if isinstance(node, str):
            codes[node] = prefix or "0"
            return
        left, right = node
        visit(left, prefix + "0")
        visit(right, prefix + "1")

    visit(heap[0][2], "")
    return codes

assert huffman_codes("") == {}
assert huffman_codes("aaaa") == {"a": "0"}
codes = huffman_codes("this is an example for huffman encoding")
assert set(codes) == set("this is an example for huffman encoding")

递增序号在频率相同时打破堆比较，避免直接比较字符串叶节点和元组内部节点。同一输入可重复得到相同码表；相同频率的字符若首次出现顺序不同，码表可能不同，但最优总长度不变。空文本返回空码表；只有一种字符时约定分配 0。若允许空码字并另存字符数，单字符还能用更短表示；这里选择便于逐个解码的约定。

合并为什么安全？ 最优满二叉前缀树中总能找到最深的一对兄弟叶节点。把频率最小的两个字符交换到这两个位置，不会增加加权路径长度。因此存在一个最优解把它们作为兄弟；并非每棵最优树都必须按同样方式排列。把这对叶节点缩成权重为两者之和的父节点，原成本等于缩小问题的成本加上这两份频率，便可继续归纳。Princeton 的压缩课程给出了 Huffman 前缀码及树的实现。

设文本长度为 N、不同字符数为 k、返回码字的长度总和为 C。计频、堆合并和构造码字共 O(N+k log(k+1)+C) 时间，额外空间 O(k+C)。这里的递归树可能很深，极端分布会触及 Python 递归限制。本函数只生成码表；完整压缩格式还需编码数据、保存解码所需的树或码长，并计算这些额外字节。

---

贪心正确性证明思路

交换论证： 假设最优解不含你的贪心选择，把最优解中的某选择和你的选择交换，证明不会变差。重复推导出包含贪心选择的最优解。

决策树

提出局部选择规则
  -> 能证明保留某个最优解：分析剩余子问题与实现成本
  -> 找到反例：放弃或修改规则，检查 DP、搜索等其他方法
  -> 暂无证明也无反例：继续验证，不能据此宣称最优

---

动手验证调度公式

下面只讨论一个处理器、每个任务耗时 1、任务可任意重排的情况。同类任务之间至少隔 n 个时间单位，可插入空闲；没有截止时间、任务依赖或不同任务时长。任务标签必须可哈希，输入可迭代。

from collections import Counter
def least_interval(tasks, n):
    if not isinstance(n, int) or n < 0:
        raise ValueError("cooldown must be a non-negative integer")
    freq = Counter(tasks)
    if not freq:
        return 0
    max_c = max(freq.values())
    max_n = sum(1 for v in freq.values() if v == max_c)
    return max(sum(freq.values()), (max_c - 1)*(n + 1) + max_n)

print(least_interval(['A','A','A','B','B','B'], 2))
# 预期: 8  (A->B->IDLE->A->B->IDLE->A->B)

设总任务数为 N，最高出现次数为 f，并列最高的类型数为 t。任何安排至少耗时 N；这些最高频类型的前 f−1 轮需要冷却间隔，最后一轮还需 t 个位置，得到下界 (f-1)(n+1)+t。按最高频类型分轮，再把其他任务填入间隔，可以达到两个下界的较大值：填不满便空闲，任务足够多便延长各轮而消除空闲。函数只返回最短长度，不生成安排；空任务返回 0，n=0 返回 N。使用哈希计频的期望时间为 O(N+1)、空间 O(u+1)，u 为不同类型数。可以用小规模状态搜索核对公式，再尝试加入截止时间，观察原证明在哪里失效。

离开单向决策路

活动选择之所以能按结束时间贪心，不是因为“越早越好”听起来直观，而是任意最优解的第一个活动都可换成最早结束者，且不会减少后续可用区间。加入权重后，这个交换不再保持目标值，于是要回到 DP。Huffman 也有自己的合并证明；不同问题不能共用一份万能贪心模板。

下一篇进入 NP 完全性与归约，学习如何区分“尚未找到好算法”和“已有复杂度证据表明问题很难”。