3. 贪心算法入门：贪心思想、活动选择问题、区间调度实战
好，咱们今天聊聊贪心算法。说实话，这名字起得挺形象——「贪心」，就是每一步都选当前看起来最好的那个。你想想看，生活中是不是也这样？比如你赶时间，肯定先做最紧急的事。贪心算法就是这个思路。
但这里有个坑：局部最优不一定等于全局最优。我在项目里就吃过这个亏，后面会细说。先别急，咱们从最经典的例子入手。
3.1 贪心思想的核心
贪心算法的核心就一句话：每一步都做出当前看来最优的选择。它不回头，不后悔，也不考虑未来。说白了，就是「走一步看一步」。
但为什么有时候它能得到全局最优解呢？因为某些问题具有一个性质——贪心选择性质。意思是，你每一步选最好的，最后拼起来就是全局最好的。这有点像搭积木，每块都选最合适的，最后搭出来的结构就是最优的。
我个人习惯把贪心算法分成三步：
- 分解问题：把大问题拆成一系列小步骤
- 确定贪心策略：每一步怎么选？按什么标准？
- 证明正确性：这个策略真的能得到全局最优吗？
嗯，第三步最难。很多初学者上来就写代码，结果发现不对。我建议你先花时间想清楚策略，再动手。
重要提醒：贪心算法不是万能的。它只适用于具有「贪心选择性质」和「最优子结构」的问题。如果你不确定，先用小规模数据测试一下。
3.2 活动选择问题
活动选择问题是贪心算法的经典入门题。场景是这样的：你有一个会议室，一天内有多个活动要举办，每个活动有开始时间和结束时间。你最多能安排多少个活动？
我在做调度系统时遇到过类似问题。当时客户说「尽量多安排会议」，我第一反应就是活动选择问题。嗯，思路完全一样。
问题定义：
- 有 n 个活动，每个活动 i 有开始时间 s[i] 和结束时间 f[i]
- 同一时间只能进行一个活动
- 目标：选择尽可能多的互不冲突的活动
贪心策略是什么？每次选结束时间最早的那个活动。为什么？因为结束得越早，留给后面的时间就越多。你想想看，是不是这个道理？
我举个例子：
| 活动 | 开始时间 | 结束时间 |
|---|---|---|
| A | 1 | 4 |
| B | 3 | 5 |
| C | 0 | 6 |
| D | 5 | 7 |
| E | 8 | 9 |
按结束时间排序后：A(1,4), B(3,5), D(5,7), E(8,9), C(0,6)。
选 A，然后找开始时间 >= 4 的，找到 D(5,7)，再找开始时间 >= 7 的，找到 E(8,9)。最终选了 A、D、E 三个活动。
代码实现也很简单：
def activity_selection(s, f):
# 按结束时间排序
activities = sorted(zip(s, f), key=lambda x: x[1])
selected = []
last_end = 0
for start, end in activities:
if start >= last_end:
selected.append((start, end))
last_end = end
return selected
# 测试
s = [1, 3, 0, 5, 8]
f = [4, 5, 6, 7, 9]
print(activity_selection(s, f))
# 输出: [(1, 4), (5, 7), (8, 9)]
小技巧：排序是关键。如果活动已经按结束时间排好序，时间复杂度就是 O(n)。否则要先排序，O(n log n)。
3.3 区间调度实战
活动选择问题其实就是区间调度的一种。区间调度更通用：给定一组区间，选出尽可能多的互不重叠的区间。
我曾经在一个物流调度项目里用过这个思路。当时要安排货车装卸货时间，每个货主给了一个时间段。我直接用贪心算法，按结束时间排序，选最早结束的。效果很好，客户很满意。
但要注意，区间调度有几种变体：
- 最大不重叠区间数：就是活动选择问题，按结束时间贪心
- 最小覆盖区间：用最少的区间覆盖整个线段，这个要按开始时间贪心
- 区间分组：把区间分成若干组，每组内不重叠，这个要用最小堆
每种变体的贪心策略都不一样。我刚开始做的时候也搞混过，后来总结了一个规律：看目标是什么，再决定按什么排序。
举个例子，区间分组问题：
def min_groups(intervals):
# 按开始时间排序
intervals.sort(key=lambda x: x[0])
import heapq
heap = [] # 存储每个组的结束时间
for start, end in intervals:
if heap and start >= heap[0]:
# 可以复用这个组
heapq.heappop(heap)
heapq.heappush(heap, end)
return len(heap)
# 测试
intervals = [(1, 4), (2, 5), (3, 6), (7, 8)]
print(min_groups(intervals)) # 输出: 3
这里用最小堆来维护每个组最晚的结束时间。每次来一个新区间，先看能不能塞进最早结束的那个组。不能的话就开新组。
避坑指南：我曾经在区间分组时忘了考虑「开始时间等于结束时间」的情况。如果区间是 [1,1] 这种点区间，它和任何区间都不冲突。记得要处理边界条件。
3.4 贪心算法的证明思路
很多同学问我：「老师，怎么证明贪心策略是对的？」说实话，这没有万能公式。但常用的方法有两个：
- 交换论证法：假设最优解和贪心解不同，通过交换元素证明贪心解不会更差
- 归纳法：证明贪心选择后，子问题仍然可以用贪心策略
拿活动选择来说，交换论证的思路是：假设最优解中第一个活动不是结束最早的，那把它换成结束最早的活动，不会影响后续选择，甚至可能更好。所以贪心解就是最优解。
嗯，证明过程有点绕。我建议你先记住结论，多做几道题，慢慢就理解了。
3.5 知识体系总览
下面这张图总结了本章的核心内容：
贪心算法虽然简单，但用好了威力很大。我见过不少调度系统，核心逻辑就是几行贪心代码。但记住，不是所有问题都能用贪心。遇到新问题时，先想想它有没有贪心选择性质，再动手。
好了，这一章就到这里。代码不多，但思想很重要。你可以在自己的项目里试试，比如安排会议、分配资源，看看贪心算法能不能帮上忙。