贪心算法入门：从局部选择到全局最优证明
插画：tokki
贪心算法每轮按照一个局部规则选择候选。真正重要的问题是：作出这个选择后，是否还保留了得到全局最优解的机会？
本文用区间调度和一维基站覆盖，展示从手算、代码到交换论证的完整过程。需要了解问题建模与排序、扫描的复杂度。
1. 局部选择与全局最优
局部最优是按当前规则挑出的选择，全局最优是满足所有约束的完整方案中目标最好的一份。贪心每步确定一个选择；枚举保留全部分支；动态规划则定义子问题，保存并复用其答案。
先看一个失败策略：“每次选开始最早的活动”。
$$ a=[0,10),\qquad b=[1,2),\qquad c=[2,3),\qquad d=[3,4) $$最早开始策略会先选 a，只得到1个活动；选 b、c、d 可以得到3个。这个反例推翻的是该策略，不是推翻整个区间调度问题存在高效算法的可能性。
这个输入中，错误规则选a，得到1项；最优可选b、c、d，共3项。一个反例就足以否定“对所有合法输入最优”的断言。它也提示我们换一个规则：优先结束得早，给后面留下更多时间。
2. 区间调度的建模与手算
输入是每项活动的开始时间与结束时间，输出是互不冲突的活动编号集合，目标是活动数量最多。
把活动写为半开区间 $[s_j,f_j)$，要求 $s_j<f_j$，且不允许拆分。$[1,4)$ 与 $[4,7)$ 可以连续安排：前一项在4结束，后一项从4开始。若增加清场时间，需要同步修改兼容条件。
2.1 沿用课件中的8个任务
沿用Introduction第27页的8个时间区间。
| 任务 | 开始时间 | 结束时间 |
|---|---|---|
| a | 0 | 6 |
| b | 1 | 4 |
| c | 3 | 5 |
| d | 3 | 8 |
| e | 4 | 7 |
| f | 5 | 9 |
| g | 6 | 10 |
| h | 8 | 11 |
本节的每个活动收益相同，目标是找一个兼容任务子集 $S$，使 $|S|$ 最大，而不是让时间轴尽量被占满。
2.2 按结束时间排序，依次扫描
排序后的顺序为 b、c、a、e、d、f、g、h。
| 当前任务 | 检查 | 决定 |
|---|---|---|
| b：$[1,4)$ | 当前还没有任务 | 选择，结束时间变为4 |
| c：$[3,5)$ | 开始时间3早于4 | 跳过 |
| a：$[0,6)$ | 开始时间0早于4 | 跳过 |
| e：$[4,7)$ | 开始时间4等于4 | 选择，结束时间变为7 |
| d：$[3,8)$ | 开始时间3早于7 | 跳过 |
| f：$[5,9)$ | 开始时间5早于7 | 跳过 |
| g：$[6,10)$ | 开始时间6早于7 | 跳过 |
| h：$[8,11)$ | 开始时间8不早于7 | 选择 |
得到 $S=\{b,e,h\}$，共3个任务。
3. 交换论证：把局部选择放进最优方案
交换论证从一个最优方案出发，把其中一个选择替换成贪心选择，并检查替换后的约束与目标。目标是证明至少存在一个最优方案包含当前选择，再利用剩余问题的相同结构继续。
直觉是尽早释放会议室，但直觉本身不是证明。可以用一次交换说明第一步没有损失：
- 取任意一个最优方案，把其中任务按时间排列，设第一个任务是 o。
- 贪心选的任务 g 在所有任务中最早结束，因此 $f_g\le f_o$。
- 用 g 替换 o 后，原方案中其余任务仍在 $f_o$ 之后开始，也就仍能接在 g 后面，任务数没有减少。
- 因而至少存在一个以 g 开头的最优方案。再对 g 结束后的剩余任务重复同样的论证。
关键不是“局部选了一个看起来不错的任务”，而是证明这一步能被某个全局最优解接纳。
排序花费 $O(n\log n)$，扫描花费 $O(n)$，总时间为 $O(n\log n)$。若输入已经按结束时间排序，扫描部分只需线性时间。
还要说明剩余问题的最优性：固定第一项g后，只保留开始时间不早于g结束的活动。若能找到更好的剩余安排，把它接在g后面就能改进原最优方案，形成矛盾。空活动集需要0项；每轮至少移除当前活动，由此可按剩余活动数量归纳。
4. 区间调度的Python实现
每项使用(名称, 开始, 结束)三元组，活动名在本例中唯一。
def interval_scheduling(jobs):
ordered = sorted(jobs, key=lambda job: (job[2], job[1], job[0]))
if any(start >= finish for _, start, finish in ordered):
raise ValueError("Each job must have start < finish")
selected = []
last_finish = float("-inf")
for name, start, finish in ordered:
if start >= last_finish:
selected.append(name)
last_finish = finish
return selected
jobs = [
("a", 0, 6), ("b", 1, 4), ("c", 3, 5), ("d", 3, 8),
("e", 4, 7), ("f", 5, 9), ("g", 6, 10), ("h", 8, 11),
]
assert interval_scheduling(jobs) == ["b", "e", "h"]
assert interval_scheduling([]) == []
assert interval_scheduling([("x", -3, -1), ("y", -1, 1)]) == ["x", "y"]
print(interval_scheduling(jobs))输出['b', 'e', 'h']。排序O(n log n)，扫描O(n)。sorted创建列表，结果也可能有n项，这份实现额外空间O(n)；已排序输入上的扫描状态本身只用常数空间，输出另计。
5. 从文字题变成一维覆盖模型
用一个基站覆盖问题，把问题建模、运行时间与最优性证明联系起来。它与前面的区间调度不同：区间调度是从已有任务中选一些，覆盖问题是决定基站放在哪里。
5.1 输入、输出和目标分别是什么
把道路看成数轴，房屋坐标为 $x_1,\ldots,x_n$；先排序，使 $x_1\le\cdots\le x_n$。允许基站放在道路的任意位置，不要求恰好在某栋房屋处。
若覆盖半径为 $r>0$，放在 b 的基站覆盖：
$$ [b-r,b+r] $$房屋 x 被覆盖，当且仅当 $|x-b|\le r$，也就是距离不超过 r。这里是闭区间，恰好距离 r 也算覆盖；不要直接沿用调度题的半开区间约定。
输出是一组基站位置，约束是每栋房屋至少被覆盖一次，目标是基站数量最少。半径 r 对应总覆盖长度 $2r$，不能混淆两者。
如果道路是有限区间 $[L,R]$，还应要求基站位置在道路内；覆盖区间超出道路的部分不影响房屋是否被覆盖。若题目改成“只能从给定候选站址中选择”，则已经改变了模型，不能直接照搬同一放置规则。
5.2 先做一个半径为2的小例子
设道路为 $[0,12]$，房屋坐标为：
$$ 1,\ 2,\ 4,\ 5,\ 9,\ 10 $$当前最左边未覆盖的房屋在1。为了覆盖它，基站位置必须在 $[-1,3]$ 与道路的交集中。把基站放在3，覆盖 $[1,5]$，前四栋房屋都被覆盖。
下一个未覆盖的房屋在9，把下一站放在11，覆盖 $[9,13]$，剩余房屋也被覆盖。虽然覆盖范围到13，基站本身在道路内的11，放置合法。
| 轮次 | 最左未覆盖房屋 | 本轮基站位置 | 本轮新覆盖房屋 |
|---|---|---|---|
| 1 | 1 | 3 | 1、2、4、5 |
| 2 | 9 | 11 | 9、10 |
本例确实至少需要两站：位置1和9相距8，大于一个基站能同时覆盖的最大两点距离4。因此两站不仅可行，也达到下界。
本例通过达到下界证明了最优性。接下来用交换论证分析一般输入上的安全选择。
6. 从局部选择到交换论证
6.1 每轮的贪心选择是什么
记 x 为当前最左未覆盖的房屋。任何覆盖 x 的基站 q，都必须满足：
$$ x-r\le q\le x+r $$暂时忽略道路右端限制，候选位置 $b=x+r$ 是仍能覆盖 x 的最右位置。它的覆盖范围为 $[x,x+2r]$。
直觉是：左侧房屋已经处理完，接下来希望尽量向右覆盖。注意这里说的是最左未覆盖，不是每轮重新从所有房屋里选最左一栋。
6.2 交换论证究竟要检查哪两条不等式
假设某个最优的剩余方案里，有一站 q 覆盖 x。尝试把 q 换成 b。
对于原来被 q 覆盖、目前尚未处理的房屋 y：
- 因为 x 最靠左，$y\ge x=b-r$。
- 因为 q 覆盖 y，且 $q\le b$，有 $y\le q+r\le b+r$。
合起来得到 $b-r\le y\le b+r$。也就是说，替换后不会丢掉任何原本由 q 覆盖的未处理房屋，站数也没有增加。
这一步真正证明的是：至少存在一个最优方案，包含我们这次的候选选择。 不要求所有最优方案都长这样，也不要求整份最优方案唯一。
这与区间调度的交换论证结构相同：替换最优方案的一部分，检查可行性不坏、目标值不差，然后处理剩余问题。两题具体替换方向不同，不能只背“都向右选”或“都选最早结束”。
6.3 为什么还要补上归纳或剩余问题论证
完成一次安全交换后，去掉新站已经覆盖的房屋，剩余的仍是同样的一维覆盖问题。
记当前房屋集合为 X，新站覆盖后剩下的集合为 $X'$，最少站数记为 $K(X)$。交换后得到一个包含 b 的最优方案，其余站覆盖了 $X'$，所以 $K(X')\le K(X)-1$。
另一方面，用 b 加上 $X'$ 的最优覆盖，就能覆盖 X，因此 $K(X)\le1+K(X')$。两个方向合起来：
$$ K(X)=1+K(X') $$没有房屋时，算法返回0站，显然最优。每轮至少覆盖当前的房屋 x，因此剩余房屋数量严格减少。按房屋数量归纳，后续选择得到 $K(X')$ 个站，本轮加1就得到 $K(X)$ 个站，整个算法最优。
6.4 道路端点与易错反例
若道路右端是 R，且 $x+r>R$，取 $b=\min(x+r,R)=R$。原方案的合法站址满足 $q\le R=b$，同时 $b-r\le x$，所以交换时仍有 $b-r\le x\le y\le q+r\le b+r$。端点截断后，证明依然成立。
训练例中，若每次直接把基站放在最左未覆盖房屋的位置，就会放在1、4、9，需要3站。它覆盖了全部房屋，却不如3、11的两站方案。这正是“可行”不等于“最优”的小反例。
7. 把算法、证明与复杂度连起来
对于任意固定覆盖半径 r，可以将覆盖算法整理成以下几个部分：
| 部分 | 你需要自己写清楚的内容 |
|---|---|
| 建模 | 房屋是数轴上的点，覆盖边界是否包含，基站允许放在哪里 |
| 算法 | 如何排序；当前处理哪栋房屋；新站位置如何确定；怎样跳过已覆盖房屋 |
| 终止性 | 每轮是否至少处理掉一栋未覆盖房屋 |
| 可行性 | 每次放站是否覆盖当前房屋；结束后是否有遗漏 |
| 安全选择 | 任意最优剩余方案中，覆盖当前房屋的站可否替换成候选站 |
| 全局最优性 | 如何把一次安全替换延续到所有轮次 |
| 复杂度 | 排序与扫描分别花多少时间，指针是否只向前移动 |
扫描时不需要反复删除数组元素或每轮从头查找。把房屋排序后，维护“下一个未覆盖房屋”的下标，覆盖一批就向前推进。每栋房屋只被推进越过一次，扫描本身是 $O(n)$；若输入无序且使用比较排序，总时间为 $O(n\log n)$。
这里的总上界包括排序，而不是“有个 while 循环所以复杂度就是线性”。额外空间还要看排序实现、是否复制输入，以及是否把输出站址数组计入；不能仅凭扫描只用一个下标，就说整个程序只占常数空间。
具体排序实现可回看排序文章。
7.1 Python实现
下面将道路端点作为参数传入，使用同一个向前移动的下标扫描房屋：
def cover_houses(houses, radius, left, right):
if radius <= 0 or left > right:
raise ValueError("Expected a positive radius and a valid road")
points = sorted(houses)
if any(x < left or x > right for x in points):
raise ValueError("Every house must be on the road")
stations = []
i = 0
while i < len(points):
station = min(points[i] + radius, right)
stations.append(station)
covered_until = station + radius
while i < len(points) and points[i] <= covered_until:
i += 1
return stations
assert cover_houses([1, 2, 4, 5, 9, 10], 2, 0, 12) == [3, 11]
assert cover_houses([9, 10], 2, 0, 10) == [10]
assert cover_houses([1, 5], 2, 0, 12) == [3]
assert cover_houses([], 2, 0, 12) == []
print(cover_houses([1, 2, 4, 5, 9, 10], 2, 0, 12))输出为 [3, 11]。循环里的 <= 对应闭区间覆盖，min 对应道路右端的限制。这里 sorted 创建了新列表，输出也保存了所有站址，因此这份实现使用 $O(n)$ 额外空间。
8. 两类交换论证的联系
| 比较项目 | 区间调度 | 一维覆盖 |
|---|---|---|
| 目标 | 活动数量最多 | 基站数量最少 |
| 贪心选择 | 最早结束的兼容活动 | 最左未覆盖点允许的最右站址 |
| 替换对象 | 最优方案的第一项活动 | 最优剩余方案中覆盖x的一站 |
| 核心不等式 | 贪心结束不晚于原第一项 | 新站右端不更左，左端仍覆盖当前点 |
| 核心保证 | 后续活动仍兼容 | 未处理房屋仍被覆盖 |
| 后续论证 | 安全首项加最优后缀 | 安全首站加最优剩余覆盖 |
两种算法使用同一种证明结构，但具体替换方向和不等式来自各自模型。
可以按五个问题组织证明：输出可行吗？当前选择能否嵌入某个最优方案？剩余问题是否同型并保持最优？每轮是否有进展从而终止？排序、扫描与存储各花多少资源？
9. 目标变为总收益后会怎样
给这8项活动增加权重，完整数据见动态规划篇。最早结束策略得到 b、e、h，总权重为：
$$ 12+13+16=41 $$而 d、h 只有两个任务，却有：
$$ 26+16=42 $$所以不能把无权问题的最优性证明直接搬过来。之前用 g 替换 o 保持了任务数量，却不一定保持收益。
这个反例说明，无权数量目标下的交换保证不再适用于任意权重。带权问题需要比较不同选择的收益，下一篇将由此定义状态和递推。
10. 练习
练习1：活动端点
[1,4)与[4,6)是否兼容？若需要1单位准备时间，兼容条件如何修改？
练习2：手动安排
A=[0,3)，B=[1,2)，C=[2,4)，D=[4,5)。写出最早结束策略的选择，与最早开始策略比较。
练习3：覆盖端点
半径2，站在3，房屋1、5、6分别是否被覆盖？为什么这里使用闭区间？
练习4：交换证明
“新站比原站靠右，所以最优”缺少哪些条件？道路[0,10]，最左未覆盖房屋9，半径2，新站在哪里？
练习5：所有最优解？
交换论证能否推出所有最优方案的第一项都必须是同一个活动？结束时间相同的两个活动应如何看待？
11. 参考答案
- 兼容，前项结束等于后项开始。增加准备时间后，按时间顺序需 $f_i+1\le s_j$，检查、图示与程序条件都应随模型调整。
- 排序B、A、C、D，选B、跳过A、选C、选D，共3项。最早开始先选A，再选D，仅2项。
- 1与5被覆盖，6没有；距离不超过r包含端点，与活动占用时间的半开约定不同。
- 要说明站址合法、不丢失原站覆盖的未处理房屋、站数不增加，并通过剩余问题完成归纳。端点例取min(9+2,10)=10。
- 只能推出至少存在一个包含贪心首项的最优解。多个最早结束活动均满足结束时间不晚于原首项，交换理由仍成立，具体输出可按固定平局规则决定。
12. 后续学习与资料
上一篇：渐进符号与函数增长率；下一篇：动态规划入门。图优化篇会把活动冲突表示成特殊区间图。
参考：Introduction第27至28页的调度模型；02Analysis第30至38页的贪心与交换论证；《第一次作业》的道路基站覆盖问题。半径2的坐标例与覆盖代码沿用原笔记。
