小学生C++信息学竞赛课程----算法选择与思维训练（7、第三章·贪心算法 第二单元排序与贪心的配合：从排队策略到区间选择大师）

第三章·贪心算法 第二单元

排序与贪心的配合：从排队策略到区间选择大师

miningweek.ca

同学们，欢迎来到贪心算法王国的第二堂课！

上一单元，我们认识了贪心算法，也知道了一个非常重要的道理：

眼前看起来最好的选择，不一定能带来最后最好的结果。

那么，真正的算法高手是怎么做的呢？

他们不会随便挑一个看起来不错的选项，而是会先观察问题的特点，设计一种选择规则，再通过推理证明这条规则确实有效。

这一节课，我们要帮助魔法学院举办一场盛大的庆典。学院准备了许多活动，但活动场地有限，同一时间只能举办一个活动。我们的任务就是安排活动，让尽可能多的活动成功举行。

在这个过程中，我们会学习：

• 算法讲解： 为什么排序经常与贪心算法配合使用？

• 图示推演： 怎样一步一步找到最优方案？

• 基础代码与模板： 如何使用struct、sort和cmp写出贪心程序？

• 典型例题： 解决活动安排、任务排队、选择课程等问题。

• 正确性证明： 学会用交换论证解释为什么贪心策略有效。

• 变式训练： 挑战最多活动、最少教室、指定时间段等更有挑战性的问题。

• 复杂度分析与自测： 不仅会写，还要知道程序为什么高效。

第一部分：算法讲解——排序为什么能帮助贪心？

一、魔法学院的活动安排难题

魔法学院要举办庆典，收到了 6 份活动申请。

kubrio.com

每个活动都有自己的开始时间和结束时间。由于学院只有一间大厅，同一时刻只能举行一个活动。

这里约定：一个活动在时间 \(t\) 结束，另一个活动恰好在时间 \(t\) 开始，两者可以连续举行，不算冲突。

例如，B 在 3 点结束，C 在 3 点开始，那么 B 和 C 可以连续安排。

1. 这道题的目标是什么？

先别急着写代码，我们先把题目翻译成人话：

• 每个活动都需要占用一段时间。

• 两个活动不能在时间上重叠。

• 我们希望安排的活动数量尽可能多。

请注意，题目不是要我们选择持续时间最长的活动，也不是要选择开始最早的活动。

我们的目标是：

\[ \boxed{\text{在互不冲突的前提下，选择尽可能多的活动}} \]

这句话就是我们设计算法时的指南针。

二、三种看似合理的选择规则

贪心算法最有趣的地方在于：同一道题，可能会有好几种看起来都不错的选择规则，但并不是每一种都正确。

我们先来做一轮策略大比拼。

策略一：每次选择开始时间最早的活动

从开始时间最早的活动入手，似乎可以让我们尽早开始庆典。

但是，如果选择 A，它从 1 点持续到 4 点，那么 B 和 C 都无法再安排。之后我们只能选择 D、E、F 中合适的活动。

例如，选择 A、D、F，最多安排 3 个活动。

可是，如果先选择 B，再选择 C、D、E、F 中不冲突的活动，就有机会安排更多活动。

所以，开始得早，不等于能够安排得多。

策略二：每次选择持续时间最短的活动

持续时间短，听起来很划算，因为短活动似乎更容易塞进日程表。

但我们不能只凭感觉。

请看这个反例：

如果先选择 A，就只能安排 1 个活动。

如果选择短活动 B、C、D、E，则可以安排 4 个活动。

因此，持续时间最短的规则也不能直接保证最优结果。

策略三：每次选择结束时间最早的活动

这一次，我们换一个角度思考：

如果想安排尽可能多的活动，那么当前活动越早结束，后面能够利用的时间通常就越多。

因此，我们尝试使用以下规则：

1. 把所有活动按照结束时间从早到晚排序。

2. 选择结束时间最早的活动。

3. 从剩下的活动中，寻找与已经选中的活动不冲突的活动。

4. 找到符合条件的活动，就选择它，并更新当前结束时间。

5. 一直检查到所有活动都处理完毕。

这就是经典的区间调度问题，也叫活动选择问题。

这里要特别强调：这个策略之所以有效，不只是因为“看起来合理”，还因为我们可以用数学推理证明它的正确性。

第二部分：图示推演——让活动排成一条时间线

一、先认识活动区间

我们可以把每个活动想象成一条横放在时间轴上的彩色积木。

观察时间线，我们会发现：

• A 与 B 重叠。

• B 与 C 可以衔接。

• C 与 D 重叠。

• D 与 E 重叠。

• E 与 F 重叠。

我们不能只看某一个活动，而要看它被选中之后，后面的活动还能不能接上。

二、按照结束时间重新排队

原来的活动按结束时间排序后是：

请注意，排序后，B 被放到了第一个位置，因为它在 3 点就结束了。

接下来我们模拟计算机的思考过程。

第一步：选择 B

B 的结束时间是 3。

当前我们已经安排了 B，所以记录：

lastFinish = 3

第二步：检查 A

A 在 1 点开始，早于 B 的结束时间 3。

判断条件：

a[i].start >= lastFinish

也就是：

1 >= 3

结果为假，所以跳过 A。

第三步：检查 C

C 在 3 点开始。

3 >= 3

结果为真！因此选择 C，并更新：

lastFinish = 5

第四步：检查 D

D 在 4 点开始。

4 >= 5

结果为假，因此跳过 D。

第五步：检查 E

E 在 5 点开始。

5 >= 5

结果为真，因此选择 E，并更新：

lastFinish = 7

第六步：检查 F

F 在 6 点开始。

6 >= 7

结果为假，因此跳过 F。

最终选择：

一共安排了 3 个活动。

这次推演最重要的不是答案 3，而是你要理解：每选中一个活动，就把“当前最早可用时间”向后推进。

图示推演小结：把选择过程变成表格

请学生记住两个变量的含义：

• ans：已经选中了多少个活动。

• lastFinish：上一个被选中活动的结束时间。

这两个变量，一个记录结果，一个记录状态，是许多贪心程序的基本结构。

第三部分：基础代码与模板——把贪心思想交给计算机

一、从活动档案开始：结构体与排序

我们先使用结构体保存每个活动的信息。

struct Activity { int start; int finish; };

为什么要用结构体？

因为一个活动有两个相互关联的信息：开始时间和结束时间。把它们放在同一个结构体里，就不会出现活动 A 的开始时间配上活动 B 的结束时间这样的错误。

接着，我们编写排序规则：

bool cmp(Activity x, Activity y) { return x.finish < y.finish; }

这段代码的意思是：如果活动x的结束时间比活动y早，就让x排在y前面。

然后调用：

sort(a, a + n, cmp);

这三个步骤——结构体保存信息、cmp定义规则、sort排序——是很多贪心题的常见组合。

二、活动选择的万能模板

#include <iostream> #include <algorithm> using namespace std; const int N = 1005; struct Activity { int start; int finish; }; Activity a[N]; bool cmp(Activity x, Activity y) { return x.finish < y.finish; } int main() { int n; cin >> n; for (int i = 0; i < n; i++) { cin >> a[i].start >> a[i].finish; } // 第一步：按照结束时间排序 sort(a, a + n, cmp); // 第二步：初始化 int ans = 0; int lastFinish = -1; // 第三步：依次检查活动 for (int i = 0; i < n; i++) { if (a[i].start >= lastFinish) { ans++; lastFinish = a[i].finish; } } // 第四步：输出答案 cout << ans << endl; return 0; }

这个模板可以记成四个动作：

1、排队

按结束时间从早到晚排序。

2、检查

判断当前活动能不能接在上一个活动后面。

3、选择

如果不冲突，就计数并更新结束时间。

4、输出

检查完所有活动，输出选中数量。

有一个小细节：lastFinish = -1适用于开始时间都不小于 0 的题目。如果题目允许负数时间，应当使用更合适的初始值，或者单独处理第一次选择。

如果题目还要求输出具体选择了哪些活动，就在选择成功时输出活动编号即可。实际竞赛中，先确认题目要求输出“数量”还是“方案”，不要多输出无关信息。

第四部分：典型例题——把贪心策略用到不同问题中

例题一：小小图书管理员

题目故事

图书馆准备举办阅读活动，每场活动都有开始时间和结束时间。一个活动结束之后，管理员才能安排下一场活动。

输入 n 个活动的时间，请输出最多能安排多少场互不冲突的活动。

输入

4 1 5 2 3 3 4 4 6

思考过程

先观察四个活动：

• 活动 1：1 到 5。

• 活动 2：2 到 3。

• 活动 3：3 到 4。

• 活动 4：4 到 6。

如果选择活动 1，那么它会占用较长的时间，其他三个活动都无法安排。

如果选择活动 2，它在 3 点结束，活动 3 可以紧接着开始；活动 3 在 4 点结束，活动 4 又可以紧接着开始。

所以我们选择：

总共安排 3 场活动。

参考程序

#include <iostream> #include <algorithm> using namespace std; struct Activity { int start, finish; }; Activity a[1005]; bool cmp(Activity x, Activity y) { return x.finish < y.finish; } int main() { int n; cin >> n; for (int i = 0; i < n; i++) { cin >> a[i].start >> a[i].finish; } sort(a, a + n, cmp); int ans = 0; int lastFinish = -1; for (int i = 0; i < n; i++) { if (a[i].start >= lastFinish) { ans++; lastFinish = a[i].finish; } } cout << ans << endl; return 0; }

输出：

3

举一反三： 题目里的活动可以换成课程、会议、电影、训练项目。只要目标是从互相冲突的时间区间中选出最多个活动，就可以考虑这套算法。

例题二：勇士的任务清单

题目故事

勇士今天有许多任务，每个任务需要占用一段时间。为了完成尽可能多的任务，勇士需要合理安排顺序。

任务如下：

按照结束时间排序：

B → C → D → A → E → F

然后开始选择：

1. 选择 B，结束时间为 2。

2. 选择 C，开始时间为 2，可以接上，结束时间更新为 4。

3. 选择 D，开始时间为 4，可以接上，结束时间更新为 5。

4. 跳过 A，因为 A 在 1 点就开始，与已选活动冲突。

5. 选择 E，开始时间为 5，可以接上，结束时间更新为 7。

6. 跳过 F，因为它在 6 点开始，与 E 冲突。

最终安排 B、C、D、E，共 4 个任务。

这里有一个值得孩子思考的问题：A 的持续时间很长，结束时间也比某些活动晚，所以它排在后面。但算法不是因为 A “不好”就跳过它，而是因为它与已经选中的活动冲突。

贪心算法的决策必须由规则和当前状态共同决定，而不是由我们对活动的主观评价决定。

参考程序：

#include <iostream> #include <algorithm> using namespace std; const int N = 1005; struct Activity { int start; int finish; }; Activity a[N]; // 按照结束时间从早到晚排序 bool cmp(Activity x, Activity y) { return x.finish < y.finish; } int main() { int n; cin >> n; for (int i = 0; i < n; i++) { cin >> a[i].start >> a[i].finish; } // 第一步：排序 sort(a, a + n, cmp); // 第二步：贪心选择 int ans = 0; int lastFinish = -1; for (int i = 0; i < n; i++) { // 当前任务可以接在上一个任务后面 if (a[i].start >= lastFinish) { ans++; lastFinish = a[i].finish; } } cout << ans << endl; return 0; }

例题三：电影节的时间安排

题目故事

一个电影节只有一块屏幕。每部电影都有开始时间和结束时间，观众希望一天能看到尽可能多部完整电影。

这与活动安排问题有什么不同？

本质上没有区别：电影就是活动，播放时间就是区间。

假设有以下电影：

按照结束时间从早到晚排序，选择：

• 魔法森林：9—11。

• 太空冒险：11—13。

• 星球旅行：13—15。

最多能看 3 部。

这个例题想教会我们什么？

算法并不认识“电影”或者“课程”这些故事名称。对于计算机来说，它只看到一组开始时间、结束时间，以及一个目标：选出最多个不冲突的区间。

这叫作抽象问题：把故事中的无关信息去掉，保留真正决定答案的数学关系。

参考程序：

#include <iostream> #include <algorithm> #include <string> using namespace std; const int N = 1005; struct Movie { string name; int start; int finish; }; Movie a[N]; bool cmp(Movie x, Movie y) { return x.finish < y.finish; } int main() { int n; cin >> n; for (int i = 0; i < n; i++) { cin >> a[i].name >> a[i].start >> a[i].finish; } sort(a, a + n, cmp); int ans = 0; int lastFinish = -1; cout << "选择的电影：" << endl; for (int i = 0; i < n; i++) { if (a[i].start >= lastFinish) { cout << a[i].name << " " << a[i].start << " " << a[i].finish << endl; ans++; lastFinish = a[i].finish; } } cout << "最多观看电影数：" << ans << endl; return 0; }

例题四：任务排队——为什么有时应该把短任务放前面？

这一题和前面的区间选择不同，但也展示了排序与贪心的配合。

题目故事

魔法学院的电脑室有一台机器，需要依次处理 4 个任务。每个任务的处理时间分别是：

5 , 1 , 3 , 2

假设机器一次只能处理一个任务，且我们希望所有任务的等待时间总和最小。

这里要区分两个概念：

• 处理时间： 机器真正执行这个任务需要多久。

• 等待时间： 任务开始执行之前，需要等待多久。

方案一：按照原顺序处理

任务时间是：

5 , 1 , 3 , 2

第一个任务等待 0 分钟；第二个等待 5 分钟；第三个等待 6 分钟；第四个等待 9 分钟。

等待时间总和：

0+5+6+9 = 20

方案二：先处理短任务

把处理时间从小到大排序：

1 , 2 , 3 , 5

等待时间分别是：

0, 1, 3，6

总等待时间：

0+1+3+6 = 10

两种排队方案对比

这道题的贪心规则是：

如果目标是最小化所有任务的等待时间总和，就考虑按处理时间从短到长排序。

注意，短任务优先不是适用于所有任务安排问题的万能规则。我们必须先确认题目要优化的是等待时间总和，而不是最晚完成时间、优先级或其他目标。

参考程序：

#include <iostream> #include <algorithm> using namespace std; const int N = 1005; int t[N]; int main() { int n; cin >> n; for (int i = 0; i < n; i++) { cin >> t[i]; } // 处理时间短的任务排在前面 sort(t, t + n); int wait = 0; // 当前任务的等待时间 int total = 0; // 所有任务等待时间总和 for (int i = 0; i < n; i++) { total += wait; wait += t[i]; } cout << "最小等待时间总和：" << total << endl; return 0; }

第五部分：重点突破——如何证明贪心策略正确？

到这里，同学们已经能识别几种常见的贪心规则：

• 活动选择：优先考虑结束时间早的活动。

• 任务等待时间：在相应条件下优先处理短任务。

• 预算选择：如果目标是购买最多件物品，且每件物品价值相同，可以考虑优先买便宜的。

但怎样证明这些规则真的正确呢？

我们重点学习一种经典方法：交换论证法。

一、用一个队列故事理解交换论证

想象一下，食堂里有两位同学要排队打饭。

• 小明只需要 2 分钟。

• 小华需要 8 分钟。

如果小明先打饭，小华后打饭：

• 小明等待 0 分钟。

• 小华等待 2 分钟。

总等待时间是 2 分钟。

如果小华先打饭，小明后打饭：

• 小华等待 0 分钟。

• 小明等待 8 分钟。

总等待时间是 8 分钟。

两个人的服务时间没有变化，只是顺序不同，结果却不一样。

因此，如果我们要让总等待时间最小，就不应该让长任务排在短任务前面。

二、把“交换”变成数学推理

假设有两个相邻任务：

• 前一个任务需要 a 分钟。

• 后一个任务需要 b 分钟。

如果先做 a ，再做 b ，这两个任务贡献的等待时间是：

0+a = a

如果先做 b ，再做 a ，贡献的等待时间是：

0+b = b

不过，在比较整个队列时，前面还有其他任务，它们已经产生的等待时间相同；后面所有任务的开始时间也会受到这两个任务总时长的影响。由于 \(a+b=b+a\)，交换这两个任务不会改变后续任务的开始时间。

所以，当 a > b时，把它们交换成 b , a 可以减少等待时间 ( a-b )。

因此，如果一个队列中出现了“长任务在短任务前面”的相邻逆序，我们就可以交换它们，而不会让总等待时间增加。

不断进行这样的交换，最后就会得到从短到长的顺序。

这就证明了：在单台机器、所有任务都需要完成、目标为最小化总等待时间且没有其他约束的条件下，短任务优先是最优策略。

这就是交换论证的魅力：不是凭感觉说“短任务优先”，而是证明任何不符合规则的顺序，都可以通过交换变得更好或不变差。

三、活动选择问题的交换证明

回到最核心的活动选择问题。

假设所有活动中，结束时间最早的活动是 G 。

我们想证明：选择 G 不会让我们错过最优答案。

第一步：假设有一个最优方案

设某个最优方案安排了：

其中 A 是这个方案中的第一个活动。

因为 G 的结束时间最早，所以：

第二步：把 A 换成 G

原方案中的第二个活动 B ，开始时间不早于 A 的结束时间。

也就是说：

又因为：

所以一定有：

因此，B 仍然可以安排在 G 后面。

后面的活动也不会受到影响。

第三步：得出结论

替换之后：

• 活动数量没有减少。

• 所有活动仍然互不冲突。

• 方案仍然是最优方案。

所以，我们可以放心地先选 G。

接着，对剩余可安排的活动重复同样的推理，就能得到整个贪心算法的正确性。

这就是区间选择算法的正确性证明。

注意：如果题目规则改变了，比如某些活动有不同价值、不同收益，目标变成“总收益最大”，那么最早结束策略未必最优。证明只对满足当前条件的问题成立。

第六部分：更有挑战性的区间问题——同样是区间，算法可能完全不同！

同学们，现在进入本节课的进阶挑战。

前面我们解决的是：

从许多互相冲突的活动中，最多能选择多少个活动？

但是，如果题目稍微变化一下，算法也可能随之变化。

这是学习算法时特别重要的能力：不要只记题目故事，要判断题目的目标究竟是什么。

例题五：如果每个活动的价值不同，怎么办？

故事：魔法学院的悬赏任务

魔法学院发布了 4 个任务。每个任务都有开始时间、结束时间，以及完成之后获得的金币。

现在目标变成了：

选择互不冲突的任务，让总奖励最大。

这和原来的活动选择问题不一样了。

原来每个活动都只算 1 个，我们只需要让活动数量最多。现在，不同任务的奖励不同，选一个高价值任务，可能比选几个低价值任务更划算。

例如：

• 选择 A、D，总奖励为 \(50+50=100\)。

• 选择 B、C、D，总奖励为 \(10+10+50=70\)。

所以，虽然 B、C、D 的任务数量更多，但总奖励反而更少。

这说明：当目标从“数量最多”变成“总价值最大”时，原来的贪心策略不能直接照搬。

这类问题通常称为带权区间调度问题。一般情况下，我们需要进一步学习动态规划，而不能简单地使用“结束时间最早”的贪心规则。

对于初学者来说，现在先记住判断方法：

参考程序：

#include <iostream> #include <algorithm> using namespace std; const int N = 1005; struct Task { int start; int finish; int reward; }; Task a[N]; int dp[N]; // 按照结束时间从早到晚排序 bool cmp(Task x, Task y) { return x.finish < y.finish; } int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i].start >> a[i].finish >> a[i].reward; } sort(a + 1, a + n + 1, cmp); dp[0] = 0; for (int i = 1; i <= n; i++) { // 方案一：不选择第 i 个任务 dp[i] = dp[i - 1]; // 方案二：选择第 i 个任务 // 找到它之前，最后一个与它不冲突的任务 int last = 0; for (int j = i - 1; j >= 1; j--) { if (a[j].finish <= a[i].start) { last = j; break; } } int choose = dp[last] + a[i].reward; if (choose > dp[i]) { dp[i] = choose; } } cout << "最大总奖励：" << dp[n] << endl; return 0; }

为了让程序更通用，我们将任务按结束时间排序，并使用动态规划记录最优奖励。

定义：

dp[i] = 只考虑排序后前 i 个任务时的最大总奖励

对于第 i 个任务，我们有两种选择：

1. 不做第 i 个任务，奖励为dp[i-1]。

2. 做第 i 个任务，把它的奖励加到所有与它不冲突的前序任务的最优答案上。

还没学习过动态规划的同学，在这里只要知道这类题目，使用贪心算法是无法得到准确最终结果的就可以。

例题六：最少需要几间教室？

故事：魔法学院扩建庆典

这一次，学院不再限制只有一间教室，而是可以增加教室。

所有活动都必须举行，但相互冲突的活动不能放在同一间教室。

问题变成：

最少需要多少间教室，才能安排全部活动？

假设有下面 5 个活动：

我们先画出活动时间线：

在时间 3 到 4 之间，A、B、C 三个活动同时进行。因此，至少需要 3 间教室。

能不能只用 3 间教室安排全部活动呢？

可以：

• 教室 1：A、D。

• 教室 2：B、E。

• 教室 3：C。

每间教室里的活动都不冲突，所以最少需要 3 间教室。

这道题为什么不能直接使用活动选择模板？

活动选择问题允许我们跳过冲突的活动，目标是“选得最多”。

但这道题必须安排所有活动，不能跳过任何一个。

因此，题目目标改变了，算法也改变了。

一种常用做法是：按照活动开始时间排序，使用最小堆维护每间教室当前最早结束的活动。

处理新活动时：

1. 如果最早结束的教室已经空出来，就让新活动使用它。

2. 如果所有教室都还被占用，就必须增加一间教室。

3. 更新该教室的结束时间。

这里的最小堆可以快速找到最早结束的活动。这种方法的时间复杂度通常是 O(n log n)。

对于还没有学习堆的同学，可以先理解问题的区别；等学完优先队列，再实现这个算法。

参考程序：

#include <iostream> #include <algorithm> #include <queue> #include <functional> using namespace std; const int N = 1005; struct Activity { int start; int finish; }; Activity a[N]; // 按照开始时间从早到晚排序 bool cmp(Activity x, Activity y) { return x.start < y.start; } int main() { int n; cin >> n; for (int i = 0; i < n; i++) { cin >> a[i].start >> a[i].finish; } sort(a, a + n, cmp); // 小顶堆：堆顶是最早结束的活动 priority_queue<int, vector<int>, greater<int> > pq; for (int i = 0; i < n; i++) { // 如果最早结束的教室已经空出来，就可以复用 if (!pq.empty() && pq.top() <= a[i].start) { pq.pop(); } // 安排当前活动，并记录它的结束时间 pq.push(a[i].finish); } cout << "最少需要的教室数：" << pq.size() << endl; return 0; }

例题七：如果活动必须在指定时间之前结束呢？

故事：午夜前的魔法表演

学院安排了一场午夜庆典，规定所有活动必须在时间 10 之前结束。

活动如下：

现在增加一个限制：不能选择结束时间大于 10 的活动。

因此，E 不符合条件，直接排除。

剩下的活动 A、B、C、D，再使用结束时间最早的贪心策略：

• 选择 A。

• 跳过 B，因为它与 A 冲突。

• 选择 C。

• 选择 D。

最后得到 A、C、D，共 3 个活动。

这道题提醒我们：贪心算法的选择规则可以与预处理、筛选条件配合使用。

参考程序：

#include <iostream> #include <algorithm> using namespace std; const int N = 1005; struct Activity { int start; int finish; }; Activity a[N]; bool cmp(Activity x, Activity y) { return x.finish < y.finish; } int main() { int n; cin >> n; for (int i = 0; i < n; i++) { cin >> a[i].start >> a[i].finish; } // 先删除无法在截止时间前完成的活动 int m = 0; for (int i = 0; i < n; i++) { if (a[i].finish <= 10) { a[m] = a[i]; m++; } } // 对剩余活动按结束时间排序 sort(a, a + m, cmp); int ans = 0; int lastFinish = -1; for (int i = 0; i < m; i++) { if (a[i].start >= lastFinish) { ans++; lastFinish = a[i].finish; } } cout << ans << endl; return 0; }

第七部分：变式训练——从会做一道题，到会识别一类题

下面的练习按照难度递进，适合课后作业或课堂分组挑战。

训练一：小小会议管理员

有 5 场会议：

请回答：

1. 按照结束时间排序后，顺序是什么？

2. 使用贪心算法，最多能安排多少场会议？

3. 具体选择哪些会议？

参考答案：

排序顺序为 A、B、C、D、E。

贪心过程：

• 选择 A，结束时间为 3。

• 跳过 B，因为 2 小于 3。

• 选择 C，结束时间为 5。

• 跳过 D，因为 4 小于 5。

• 选择 E，结束时间为 7。

最终选择 A、C、E，共 3 场。

训练二：勇士的时间管理

有 6 个活动：

请使用结束时间最早的策略，求最多能安排多少个活动。

参考答案：

按照结束时间排序后：

B、C、D、E、A、F。

依次选择：

• B：2—3。

• C：3—4。

• D：4—6。

• E：6—7。

• F：7—9。

A 与已选活动冲突，跳过。

最终选择 B、C、D、E、F，共 5 个活动。

训练三：判断贪心规则

请判断下面的说法是否正确，并说明理由。

1. 活动选择问题中，每次挑开始时间最早的活动，一定能安排最多的活动。

2. 活动选择问题中，按照结束时间从早到晚排序，可以使用经典贪心策略。

3. 只要先排序，再从前往后选，就一定是正确的贪心算法。

4. 如果每个任务奖励不同，目标是总奖励最大，那么结束时间最早的策略仍然一定正确。

参考答案：

1. 错。开始最早的活动可能占用很长时间。

2. 对。对于经典的“最多选择互不冲突区间”问题，这个策略可以通过交换论证证明。

3. 错。排序规则必须与目标匹配，还需要证明策略正确。

4. 错。奖励不同以后，问题变成带权区间调度，通常需要动态规划等方法。

训练四：最少需要多少间教室？

活动如下：

请回答：

1. 最少需要多少间教室？

2. 为什么不能直接用“选择最多个不冲突活动”的算法？

参考答案：

最少需要 3 间教室，因为在时间 3 到 4 之间，A、B、C 三个活动同时进行。

活动选择算法会跳过与已选活动冲突的区间，不能保证所有活动都被安排，因此不适用于这个目标。

训练五：挑战题——贪心算法是否适用？

有 4 个活动：

要求选择互不冲突的活动，让总奖励最大。

请比较：

• 方案一：A、D。

• 方案二：B、C、D。

哪一个方案更好？能不能只按照结束时间最早排序，便得到总奖励最大的方案？

参考答案：

方案一的奖励为 40+40 = 80。

方案二的奖励为 15+15+40 = 70。

方案一更好。

这道题的重点是提醒我们：如果每个区间的价值不同，不能把“数量最多”的贪心策略直接当作“总价值最大”的策略。

第八部分：复杂度分析——为什么排序加贪心很高效？

我们再从计算机的角度，分析活动选择算法的运行速度。

假设有 n 个活动。

一、排序需要多久？

sort(a, a + n, cmp);

C++ 的sort通常需要：

O(nlog n)

二、扫描活动需要多久？

for (int i = 0; i < n; i++) { if (a[i].start >= lastFinish) { ans++; lastFinish = a[i].finish; } }

这个循环从第 0 个活动检查到第 \(n-1\) 个活动，每个活动只检查一次。

因此：

O(n)

三、总复杂度是多少？

排序和扫描加起来：

O(nlog n+O(n) = O(nlog n)

因为当 n 足够大时，n log n 的增长速度比 n 更快，所以总复杂度由排序部分决定。

空间方面，程序使用 O(n) 的数组存储活动；sort自身的额外空间开销通常为 O(log n) 量级，具体实现细节由标准库实现决定。

四、和暴力枚举比较

如果有 n 个活动，每个活动都可以选择或不选择，那么总共有：

2^n

种可能的子集。

如果我们逐个枚举所有子集，再判断每个子集是否互不冲突，算法的时间复杂度可能达到 O(n2^n）。

而排序加贪心只需要：

O(nlog n)

这就是贪心算法的一个重要优势：通过正确的选择规则，避免检查大量没有必要的方案。

但请注意，运行速度快不代表策略一定正确。必须先证明算法正确，再讨论复杂度。

第九部分：课堂自测——你真的掌握贪心算法了吗？

下面 8 道题，从基础理解逐步走向算法思维。建议让学生先独立完成，再查看答案。

贪心算法自测

1. 经典活动选择问题的目标是什么？

A. 选择持续时间最长的活动

B. 选择最多个互不冲突的活动

C. 选择开始时间最早的活动

正确答案：B

题目要求活动数量尽可能多，而不是单独挑选最长或最早开始的活动。

2. 经典活动选择问题应该优先按照什么排序？

A. 开始时间从早到晚

B. 持续时间从短到长

C. 结束时间从早到晚

正确答案：C

最早结束的活动能够尽早释放时间，为后续活动留下更多机会。

3. 上一个活动 5 点结束，当前活动 5 点开始，能否选择？

A. 可以

B. 不可以

C. 必须看活动名称

正确答案：A

本课约定结束时间等于下一个活动的开始时间时，两者可以衔接。

4. 活动选择程序中，lastFinish 保存什么？

A. 所有活动中最大的结束时间

B. 上一个被选中活动的结束时间

C. 当前活动的开始时间

正确答案：B

它用于判断当前活动能否接在已选活动后面。

5. 为什么要先排序再扫描？

A. 为了让程序看起来更整齐

B. 为了按照正确的选择规则依次检查活动

C. 因为 sort 能自动找出最优答案

正确答案：B

排序提供检查顺序，但真正做出选择的仍是贪心判断。

6. 如果任务奖励不同，目标是总奖励最大，最早结束策略一定正确吗？

A. 一定正确

B. 不一定，需要重新分析问题

C. 只要任务数量超过 10 就正确

正确答案：B

奖励不同后，目标不再只是最大化活动数量，通常需要考虑带权区间调度。

7. 排序加线性扫描的总时间复杂度通常是什么？

A. O(n)

B. O(n log n)

C. O(2^n)

正确答案：B

排序需要 O(n log n)，扫描需要 O(n)，合起来为 O(n log n)。

8. 交换论证的核心思想是什么？

A. 随便交换两个活动

B. 证明把最优方案中的某一步换成贪心选择，不会让结果变差

C. 只比较程序运行速度

正确答案：B

交换论证通过保持可行性和目标值不变差，证明贪心选择是安全的。

第十部分：本单元的最终总结

同学们，今天我们学的不只是一个活动选择模板，而是三种重要的算法能力。

能力一：找到合适的排序规则

排序不是目的，而是为了让后续选择更有规律。经典活动选择问题按结束时间从早到晚排序；最小化任务等待时间的问题，在相应条件下按处理时间从短到长排序。

能力二：证明选择规则正确

不能只说“我觉得这样比较好”。交换论证可以帮助我们证明：用贪心选择替换最优方案中的某一步，不会让最终结果变差。

能力三：识别题目目标的变化

最多选择几个区间、让总奖励最大、安排全部区间所需教室最少，是三个不同的问题。故事可能相似，但算法不能直接照搬。

贪心算法的思考口诀

先看目标，再定规则；

先做排序，再来选择；

反例检验，证明正确；

复杂度算，代码落地。

最后，希望同学们牢牢记住：贪心算法并不是“每次随便挑一个最好的”，而是找到一种能够被证明有效的局部选择规则，并利用它一步步构造出全局最优解。