第14章：贪心算法

---

元数据卡

字段	值
难度等级	（看起来简单，陷阱不少）
前置章节	第13章 动态规划、第8章 图（MST/最短路径部分）
核心思想	局部最优 → 全局最优（但别信得太早）
实战出镜率	工程中极高（路由、调度、编码）
读本章姿势	对比第13章看 → 学会什么时候该 DP，什么时候该贪心

---

你的进度

不是所有问题都需要想那么复杂。有时，在每一步都选当下最好的——不做后悔药、不回头看——就是全局最优解。

上一章你被 DP 折腾得够呛——状态定义、转移方程、遍历顺序，每一步都要精算。你问自己："有没有更简单的方法？"

答案是：有，但条件苛刻。

贪心算法就是那个看起来"偷懒"的解法：每次只选当前最好的，从不回头。DP 是全局扫描的望远镜，贪心是"走一步看一步"的指南针。

这一章讲的是：什么时候指南针不会带你绕远路，什么时候会。

---

你的任务

本章分层

• 必读：贪心选择性质的核心含义（局部最优 → 全局最优的条件）；活动选择问题（选最早结束的）；区间调度基本版
• 选读：加权区间调度（贪心不行→DP）；哈夫曼编码（能理解概念即可，不要求完整实现全套）
• 进阶：贪心选择性质的数学证明方法（反证法+交换论证）

本章不会要求你掌握

• MST（Kruskal / Prim）的完整实现——回到图算法章节去学
• Dijkstra 最短路径——回到图算法章节
• 哈夫曼编码的完整树构建和编码表生成（了解概念即可）

上午你刚用 DP 解决了一个背包问题——状态 2D 数组、O(nW) 时间、跑得还行。

然后驿站管事来了：

"背包问题不是需求。我们要做一个林间驿站日程安排：一天有 N 批冒险者要使用篝火营地，每批有开始时间和结束时间，怎么排才能让最多的人用上？"

这几个问题如果用 DP 来做，能解，但有点杀鸡用牛刀。你要学习的是：什么时候该用大刀（DP），什么时候用小刀（贪心）。

---

破局 · 溯源

情景：篝火营地的选择

驿站前张贴了 6 份篝火营地使用申请：

申请项目	开始	结束
晨间训练	9:00	10:30
物资清点	9:30	11:00
兵器维护	10:30	11:30
林间会议	11:00	12:00
一对一指导	11:30	12:30
午间休整	12:00	13:00

你用了 DP 算了一个最优安排，结果发现：最早结束的活动永远应该被选上，然后剩下的子问题结构和原问题一模一样。

** 技能获得：贪心选择性质**

"一个全局最优解可以通过一系列局部最优选择来达到。"

活动选择问题的贪心策略：每次都选结束时间最早且与已选活动不冲突的那个。

# 活动选择 —— 贪心
def activity_selection(activities):
 # activities: list of (start end)
 activities.sort(key=lambda x: x[1]) # 按结束时间排序
 selected = [activities[0]]
 last_end = activities[0][1]
 for start end in activities[1:]:
 if start >= last_end:
 selected.append((start end))
 last_end = end
 return selected

acts = [(9 10.5) (9.5 11) (10.5 11.5) (11 12) (11.5 12.5) (12 13)]
result = activity_selection(acts)
print([f"{s:.0f}:00-{e:.0f}:00" for s e in result])
# 输出: ['9:00-10:30' '10:30-11:30' '11:30-12:30']

换个角度想——如果选"最早结束的"不成立呢？ 那这条贪心就直接废了。但在这道题上，数学证明它是成立的。

** 清醒剂：** 贪心不是说"当前最优就是全局最优"——这句话只有在问题满足贪心选择性质和最优子结构时才成立。而你是不是满足了，需要数学证明。

---

常见陷阱

1. 贪心选择性质——你需要理解的核心

DP 和贪心的共同点：都需要最优子结构。

不同点：

维度	动态规划	贪心算法
决策方式	枚举所有选择	当前一步选最优
回头看吗？	会（通过子问题结果）	从不回头
证明难度	靠转移方程推导	需要独立证明
时间复杂度	O(n²) ~ O(n³) 起	O(n log n) 或 O(n)
正确性保障	数学归纳	贪心选择性质证明

贪心选择性质： 做出一个局部最优选择后，剩余子问题的最优解 + 这个局部最优选择 = 原问题的最优解。

这是贪心算法能用的充要条件——没有这个，你就是在赌。

---

2. 区间调度（Interval Scheduling）

上面说的活动选择是区间调度的一个特例。广义区间调度还有更复杂的变种：

加权区间调度（Weighted Interval Scheduling） ——每个活动有不同权重，选权重和最大的互不冲突集。

这就是贪心失灵的例子了——你没法单纯用"最早结束"来选，因为可能有个权重大的长活动和几个小短活动冲突。这时候你需要 DP。

# 加权区间调度——贪心不行！得用 DP
def weighted_interval_scheduling(intervals):
 # intervals: list of (start end weight)
 intervals.sort(key=lambda x: x[1]) # 按结束时间排序
 n = len(intervals)
 dp = [0] * (n + 1)
 # p[i]: 与第 i 个活动不冲突的最近前一个活动的索引
 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 # +1 因为 dp 是 1-indexed
 for i in range(1 n + 1):
 dp[i] = max(dp[i - 1] intervals[i - 1][2] + dp[p[i - 1]])
 return dp[n]

# 测试：权重大但冲突多的活动
ivs = [(9 11 5) (10 11 1) (11 12 1)]
print(weighted_interval_scheduling(ivs)) # 输出: 5 (选第一个)

** 启示：** 同样是活动选择问题，有无权重决定了你能不能贪心。

---

3. 哈夫曼编码（Huffman Coding）——理解概念即可

哈夫曼编码是贪心在数据压缩中的经典应用。 理解核心思路即可，不要求手写完整实现。

给你一串字符，每个字符有出现频率。设计一个二进制编码，让编码后的总长度最短。

这是贪心算法在数据压缩领域的经典应用。

思路： 每次合并频率最小的两个节点，构建一棵二叉树。左分支为 0，右分支为 1。路径就是编码。

import heapq
from collections import Counter

class HuffmanNode:
 def __init__(self char freq):
 self.char = char
 self.freq = freq
 self.left = None
 self.right = None
 def __lt__(self other):
 return self.freq < other.freq

def huffman_encoding(text):
 if not text:
 return {} ""
 freq = Counter(text)
 heap = [HuffmanNode(c f) for c f in freq.items()]
 heapq.heapify(heap)
 # 合并最小频率的两个节点
 while len(heap) > 1:
 left = heapq.heappop(heap)
 right = heapq.heappop(heap)
 merged = HuffmanNode(None left.freq + right.freq)
 merged.left = left
 merged.right = right
 heapq.heappush(heap merged)
 # 生成编码表
 codes = {}
 def build_codes(node code=""):
 if node:
 if node.char is not None: # 叶子节点
 codes[node.char] = code
 build_codes(node.left code + "0")
 build_codes(node.right code + "1")
 build_codes(heap[0])
 encoded = "".join(codes[c] for c in text)
 return codes encoded

text = "this is an example for huffman encoding"
codes encoded = huffman_encoding(text)
print(f"原始长度: {len(text) * 8} bits")
print(f"压缩后长度: {len(encoded)} bits")
print(f"压缩率: {len(encoded) / (len(text) * 8):.1%}")
# 输出示例:
# 原始长度: 288 bits
# 压缩后长度: 135 bits
# 压缩率: 46.9%

// Java: 哈夫曼编码核心逻辑（使用 PriorityQueue + 树结构）
// 代码结构与 Python 版本对应，使用 Comparator.comparingInt 排序
// 预期行为相同：合并最小频率节点 → 构建编码树 → 生成前缀码

为什么哈夫曼贪心是正确的？

• 两个频率最小的字符一定在最底层（最优前缀码性质）
• 合并后的结构和原问题结构一致（最优子结构）
• 所以贪心选择一直做下去就是全局最优

---

回到图算法章节：最小生成树（Minimum Spanning Tree MST）

MST 本质上是图算法，不是贪心入门的最佳例子。 这里的介绍作为预览，完整的 Kruskal/Prim 实现放在图算法章节。

一个连通的无向图，选择 n−1 条边，连通所有顶点，且边权重和最小。

Kruskal 算法——按边贪心

策略： 每次选权重最小的边，只要不形成环。

class UnionFind:
 def __init__(self n):
 self.parent = list(range(n))
 self.rank = [0] * n
 def find(self x):
 if self.parent[x] != x:
 self.parent[x] = self.find(self.parent[x])
 return self.parent[x]
 def union(self x y):
 rx ry = self.find(x) self.find(y)
 if rx == ry:
 return False
 if self.rank[rx] < self.rank[ry]:
 self.parent[rx] = ry
 elif self.rank[rx] > self.rank[ry]:
 self.parent[ry] = rx
 else:
 self.parent[ry] = rx
 self.rank[rx] += 1
 return True

def kruskal(n edges):
 # edges: list of (weight u v)
 edges.sort()
 uf = UnionFind(n)
 mst_weight = 0
 mst_edges = []
 for w u v in edges:
 if uf.union(u v):
 mst_weight += w
 mst_edges.append((u v w))
 return mst_weight mst_edges

# 图示例
edges = [(1 0 1) (2 1 2) (3 0 2) (4 1 3) (5 2 3)]
print(kruskal(4 edges))
# 输出: (7 [(0 1 1) (1 2 2) (1 3 4)])

Prim 算法——按顶点贪心

策略： 从一个点开始，每次选连接已选集合和未选集合的最小边。

import heapq

def prim(n graph):
 # graph: adjacency list [(neighbor weight)]
 visited = [False] * n
 min_heap = [(0 0 -1)] # (weight vertex parent)
 mst_weight = 0
 mst_edges = []
 while min_heap:
 w v parent = heapq.heappop(min_heap)
 if visited[v]:
 continue
 visited[v] = True
 mst_weight += w
 if parent != -1:
 mst_edges.append((parent v w))
 for to weight in graph[v]:
 if not visited[to]:
 heapq.heappush(min_heap (weight to v))
 return mst_weight mst_edges

# 图示例（邻接表）
graph = [
 [(1 1) (2 3)] # 0: 连 1(权1) 和 2(权3)
 [(0 1) (2 2) (3 4)] # 1
 [(0 3) (1 2) (3 5)] # 2
 [(1 4) (2 5)] # 3
]
print(prim(4 graph))
# 输出: (7 [(0 1 1) (1 2 2) (1 3 4)])

// C++: Kruskal 关键片段（排序 + Union-Find）
// sort(edges.begin() edges.end()); // 按权重排序
// DSU dsu(n);
// for (auto& [w u v] : edges)
// if (dsu.unite(u v)) { mst_weight += w; }

算法	贪心对象	数据结构	时间复杂度	适用场景
Kruskal	边（全局最小）	并查集	O(E log E)	边少（稀疏图）
Prim	顶点相连的最小边	优先队列	O(E log V)	边多（稠密图）

** 常见坑：** Kruskal 必须用并查集检测环。有人用 BFS 判断 —— 那每加一条边就 O(V+E)，直接退化成 O(E²)。并查集是 MST 问题的标配，不是选配。

---

回到图算法章节：Dijkstra 最短路径——单源贪心

Dijkstra 是最短路径算法，完整内容在图算法章节。 这里作为贪心的一个例子简要提及，不展开。

从一个起点出发，到图中所有其他点的最短路径。要求图中边权为非负数。

策略： 每次从未处理的顶点中选距离起点最近的那个，用它的邻居更新距离。

import heapq

def dijkstra(n graph start):
 # graph: adjacency list [(to weight)]
 dist = [float('inf')] * n
 dist[start] = 0
 pq = [(0 start)] # (distance vertex)
 while pq:
 d u = heapq.heappop(pq)
 if d > dist[u]:
 continue
 for v w in graph[u]:
 if dist[u] + w < dist[v]:
 dist[v] = dist[u] + w
 heapq.heappush(pq (dist[v] v))
 return dist

graph = [
 [(1 4) (2 1)]
 [(3 1)]
 [(1 2) (3 5)]
 []
]
print(dijkstra(4 graph 0)) # 输出: [0 3 1 4]

Dijkstra 为什么是贪心？ 因为它每次选"当前距离最小"的顶点，一旦标记为已处理，距离就不再更新。这个选择是基于一个假设：非负边权下，不可能有绕路比直接路径更短。

为什么边权不能为负？ 如果边有负权，一个已经"处理"过的顶点可能通过负权边找到更短的路径——贪心就废了。负权边 → 用 Bellman-Ford。

// Java: Dijkstra 实现
public int[] dijkstra(int n List<int[]>[] graph int start) {
 int[] dist = new int[n];
 Arrays.fill(dist Integer.MAX_VALUE);
 dist[start] = 0;
 PriorityQueue<int[]> pq = new PriorityQueue<>(
 Comparator.comparingInt(a -> a[1])
 );
 pq.offer(new int[]{start 0});
 while (!pq.isEmpty()) {
 int[] cur = pq.poll();
 int u = cur[0] d = cur[1];
 if (d > dist[u]) continue;
 for (int[] edge : graph[u]) {
 int v = edge[0] w = edge[1];
 if (dist[u] + w < dist[v]) {
 dist[v] = dist[u] + w;
 pq.offer(new int[]{v dist[v]});
 }
 }
 }
 return dist;
}
// 预期输出: [0 3 1 4]

---

6. 贪心 vs DP 对比表

这是全文的精髓。把这两章读完，你唯一需要记住的就是这张表：

对比维度	贪心算法（Greedy）	动态规划（DP）
哲学	只看眼前，从不回头	记住所有可能性
依赖条件	贪心选择性质 + 最优子结构	重叠子问题 + 最优子结构
时间复杂度	通常 O(n log n) 或更低	通常 O(n²) 起
空间复杂度	常 O(1) 或 O(n)	通常 O(n) ~ O(n²)
正确性保障	需要独立数学证明	转移方程推导
回溯需求	无	需要子问题结果
典型问题	活动选择、霍夫曼、MST、Dijkstra	背包、LCS、编辑距离、TSP
工程适用	实时系统、路由协议（快！）	离线计算、规划（准！）
翻车概率	高（以为有贪心性质其实没有）	低（只要能写出转移方程就对了）

面试决策树：

问题是不是最优化问题？
 ├── 否 → 搜索/排序/模拟
 └── 是 → 尝试证明贪心选择性质
 ├── 能证明 → 用贪心（快且简洁）
 └── 不能证明 → DP（稳但慢）
 └── 还是觉得不对 → 回溯剪枝

真实面试场景模拟：

面试官："你用了 DP，但这个问题能不能用贪心？" 你："我怀疑不能。因为如果我用贪心策略做 max(dp[i-1] dp[i-2] + nums[i])，它会丢失一种可能——就是当前这个权重太大导致和更早的选择冲突。让我举例证明一下..." 面试官点头。这就是满分回答。

---

通关挑战

挑战 1：任务调度器（Task Scheduler）

给你一个任务列表 tasks = ['A''A''A''B''B''B']，每个任务执行需 1 单位时间。相同任务之间必须有 n 单位的冷却时间（n=2）。求最短执行时间。

from collections import Counter

def least_interval(tasks n):
 freq = Counter(tasks)
 max_count = max(freq.values())
 max_num = sum(1 for v in freq.values() if v == max_count)
 return max(len(tasks) (max_count - 1) * (n + 1) + max_num)

tasks = ['A''A''A''B''B''B']
print(least_interval(tasks 2)) # 输出: 8
# 调度: A→B→IDLE→A→B→IDLE→A→B

挑战 2：划分字母区间（Partition Labels）

字符串 S，划分成尽可能多的片段，每个字母最多出现在一个片段中。

def partition_labels(s):
 last = {c: i for i c in enumerate(s)}
 start = end = 0
 result = []
 for i c in enumerate(s):
 end = max(end last[c])
 if i == end:
 result.append(end - start + 1)
 start = i + 1
 return result

print(partition_labels("ababcbacadefegdehijhklij"))
# 输出: [9 7 8]
# 解释: "ababcbaca" | "defegde" | "hijhklij"

---

验收标准

学完这章，你需要能：

1. 用自己的话解释"贪心选择性质"——给一个满足的和不满足的例子
2. 手写活动选择问题的贪心解法，并说明为什么选"最早结束"
3. 对比 Kruskal 和 Prim，说出各自依赖的数据结构和适用场景
4. Dijkstra 算法为什么不能处理负权边？举一个负权边导致出错的具体例子
5. 什么时候该用贪心，什么时候该用 DP？（用上面的决策树回答）
6. 给一个你觉得能用贪心但实际上不能的问题，并证明它不行

---

常见卡点

卡点	症状	怎么办
以为所有最优化都能贪心	一上来就写贪心，跑完发现不对	必须问自己："能不能举一个反例？"
Dijkstra 写了负权边	结果错了，还不知道错在哪	检查边权——有负数就用 Bellman-Ford
Kruskal 循环检测太慢	每次加边都 BFS	用并查集，路径压缩 + 按秩合并
区间问题不分权重	加权区间调度也写贪心	看清楚：有权重 → DP，无权重 → 贪心
证明不会写	面试让证明贪心正确性就卡住	用反证法：假设最优解不包含贪心选择 → 用交换法推出矛盾

---

现在不需要理解

• 拟阵理论（Matroid Theory）——贪心算法正确性的数学基础，学界研究多于工程用
• 贪心算法的近似比证明——组合优化的内容
• 在线算法（Online Algorithm）的竞争比——算法博弈论方向
• 次模函数最大化（Submodular Maximization）——机器学习高级话题

---

旅人笔记

我大学时第一次学贪心算法，觉得这玩意儿太朴素了——"每次选最好的，这也叫算法？"然后我在一次林中演练里用了贪心做物资路线规划，结果被实际的地形数据打脸。那个教训让我记住了：贪心看起来简单，但你要证明它有效，比 DP 的转移方程还难。

后来在分布式系统中做一致性哈希、在消息队列里做优先级调度、在 CDN 里做最近节点路由——我才发现生产环境到处都是贪心，因为要么实时性要求高（DP 来不及），要么状态空间太大（DP 存不下）。

贪心最好的老师不是书本，是生产环境的线上故障报告。

顺便说一句：如果你面试时拿出一道题，然后说"这道题可以用贪心，我们来证明一下"，面试官会给你加分的——因为他们见过太多人只会背代码。

---

→ 下一站预告

前面两卷是"地基"和"材料"。Vol 3 开始进入 "设计" 层面——设计模式、系统架构、分布式系统。

但在此之前，建议你打开 LeetCode 或 Codeforces，分别刷 30 道 DP 和 15 道贪心。这两个算法是所有算法面试的"基本盘"——会了不一定过，不会一定挂。而且你会发现一个奇妙的事情：刷到后面，贪心和 DP 的边界越来越模糊——有些问题既可以用 DP 解也可以用贪心解，区别只是时间和空间的权衡。

这就是算法设计的美妙之处：同一个问题，不同思维模型，不同解法。你的工具箱里多了两个选择——现在你要做的，就是学会在正确的时间选正确的工具。