贪心算法入门：C语言实现活动选择问题详解

从大一开始刷算法题，活动选择问题（Activity Selection Problem）是我遇到的第一道真正让我“哇”出声的贪心题。它不靠复杂的语法，也不需要高深的数据结构，但能把“贪心算法”四个字讲透：每次选一个看起来最有利的局部选项，最后居然能拼出全局最优解。实际应用里，会议室预订、教室排课、单台机器上的任务调度，本质上都能抽象成这个问题。如果你正在学 C 语言的指针、结构体和排序，又想入门贪心，这篇文章正好对症。我会从问题建模、贪心策略、C 语言实现、调试经验一路讲到延伸题型，每一步都会交代清楚为什么这么选。

1. 贪心思路与活动选择问题建模

1.1 先把问题说清楚

活动选择问题的标准描述是这样的：有 n 个活动，每个活动 i 有一个开始时间 s_i 和结束时间 f_i，其中 s_i < f_i。如果你安排了活动 i，那么在 [s_i, f_i) 这段时间里就不能安排其他活动。目标是选出尽可能多的活动，让它们彼此之间没有时间重叠。注意，这里约定：如果一个活动结束时间是 4，另一个活动开始时间也是 4，那么这两个活动是可以连着安排的，因为端点上没有重叠。

举个例子，假设有 5 个活动：

肉眼扫一遍，能选出的最多数量是 3：A1（1到3）、A3（3到5）、A5（5到8）。这三个活动首尾相接，没有任何冲突。当然，A1、A2、A5 不行，因为 A1 和 A2 在 2 到 3 这段时间重叠了。这个问题看似简单，但如果活动数量涨到几千甚至几万个，靠肉眼和深搜都撑不住，必须找一个有规律的高效策略。

这类问题最经典的使用场景，是学校机房管理老师的排课。每个培训班申请一个时间段用机房，同时间只能容纳一个班，机房管理员想接待最多的培训班，他该按什么顺序答应？这就是活动选择问题的现实版。

1.2 为什么“选结束时间最早”是正确策略

对于贪心算法，大多数人的第一反应可能是“先选开始最早的”。这个想法很符合直觉：开始得早，好像就能多利用时间。但例子立刻推翻它：如果一个活动从 0 开始，一直持续到 100，另一个活动从 1 到 2，第三个从 3 到 4。选开始最早的那个，结果只能选到 1 个活动；而选两个短活动，能选到 2 个。

还有人会想“选持续时间最短的”。在部分例题里它能碰巧通过，但同样能找到反例：有一个跨全天的大活动，还有两个稍微重叠的中等活动，持续时间最短的一个小活动放在中间，会挡住两个中等活动的连接。贪心策略最大的坑就在这里——局部看起来最优，全局未必最优。

那为什么“每次选结束时间最早，然后继续选下一个与它不冲突的活动”就一定对呢？关键在于，结束时间越早，留给后面的自由时间就越长。假设你在做日程安排，手头有两个候选活动，一个下午三点结束，一个下午五点结束。选三点结束的，四点之后的时间还可以再安排别的事情；选五点结束的，四点之后的安排就泡汤了。从“最大化后续可选空间”这个角度看，三点结束的活动永远不亏。

严格证明可以用交换论证：假设某个全局最优解里，第一个选中的活动是 x，而贪心算法第一个选中活动是 g。因为 g 是所有活动中结束时间最早的，所以 g 的结束时间一定不晚于 x 的结束时间，也就是 f_g ≤ f_x。我们可以安全地在这个最优解里把 x 替换成 g，替换之后，和后面的活动依然不冲突，甚至留出的空隙更大。于是我们得到了一个新的最优解，它的第一个活动和贪心选择一致。接着对剩下的活动重复同样的推理，每一步贪心都能替换到某个最优解里，所以贪心最终得到的就是最优解。

这个证明思路值得记下来，因为很多贪心算法题的正确性都可以用“交换论证”来说明：先假设最优解和贪心解第一个不同，再把最优解里的对象换成贪心对象，看看会不会变差，不会变差就说明贪心没毛病。

1.3 活动选择其实是动态规划的特例

学过一点动态规划的朋友可能会发现，活动选择问题也可以写成递归式：dp[i] 表示前 i 个活动里能选出的最多活动数，转移的时候要判断选不选第 i 个活动。动态规划当然能解，但时间复杂度通常是 O(n^2)，因为每个活动都要回头找上一个能接得上的活动。

但贪心算法的聪明之处在于，当活动按照结束时间排序后，每次选择都不会影响后续子问题的最优结构。你选完当前结束最早的活动，剩下要处理的只是“所有开始时间不早于当前结束时间的活动”，这是一个独立子问题，不需要回看之前的状态。因此它退化成了“一路顺手选下去”的线性过程，只需要 O(n) 遍历，加上排序一共 O(n log n)。这也解释了为什么活动选择被称为动态规划中最适合用贪心求解的一类：它天然满足“一个选择只留一个子问题”的条件，而不像爬楼梯或者背包那样需要同时考虑多个子问题。

2. C 语言代码实现与关键细节

2.1 用结构体把开始时间和结束时间绑在一起

如果你刚学 C 语言，可能会写出两个独立数组：一个 int start[1005]，一个 int end[1005]。这样写倒不是不行，但一旦排序就会很痛苦。你用 qsort 对数组排序后，开始时间和结束时间的对应关系很容易乱掉。活动选择问题里，“开始时间”和“结束时间”必须成对移动，所以我一般会定义一个结构体：

typedef struct { int start; int end; } Activity;

以后在代码里看到 activities[i].start 和 activities[i].end，语义一目了然，比调用 start[i] 和 end[i] 直观得多。数组大小可以根据题目要求调整，如果没有特别说明，可以先开一个足够大的固定数组，例如 10005；也可以在学完动态内存分配之后，用 malloc 按实际 n 来申请。对刷算法题来说，固定数组更省心，也避免处理 malloc 失败的问题。

2.2 qsort 排序的正确写法

C 语言标准库提供了 qsort，可以对任意类型的数组排序，但前提是你得告诉它怎么比较两个元素。这里最容易出错的，是函数原型：

void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));

比较函数必须接收 const void * 类型，所以第一步要强转成 Activity *。我的习惯写法是：

int cmp(const void *a, const void *b) { const Activity *x = (const Activity *)a; const Activity *y = (const Activity *)b; if (x->end != y->end) { return (x->end > y->end) - (x->end < y->end); } return (x->start > y->start) - (x->start < y->start); }

这里有两个细节。第一，如果只按结束时间排序，那么结束时间相同的活动顺序无所谓；不过加上“结束相同按开始时间从大到小”之后，输出会更整齐，调试时也更容易对比。第二，我故意没有写 return x->end - y->end，虽然大部分题目里这样写也正确，但当 x->end 是 2147483647、y->end 是 -2147483647 时，相减会溢出，产生未定义行为。写成 (x->end > y->end) - (x->end < y->end) 则永远安全，因为表达式里只包含大小比较。这也是很多 C 语言笔试题会挖坑的地方。

2.3 贪心选择的循环怎么写

排序之后，核心代码其实只有几行。定义一个变量 last_end，表示上一个被选中的活动的结束时间。初始时，还没有选任何活动，所以 last_end 可以设置成一个足够小的数，比如 -1。然后从头遍历排好序的活动数组：

int ans = 0; int last_end = -1; for (int i = 0; i < n; i++) { if (activities[i].start >= last_end) { printf("选中活动: [%d, %d]\n", activities[i].start, activities[i].end); ans++; last_end = activities[i].end; } }

判断条件是 start >= last_end，意味着当前活动的开始时间不早于上一个活动的结束时间，二者可以在同一点首尾相接。如果题目要求“两个活动之间必须有间隔”，那就把 >= 改成 >。现实里的会议室预订通常允许前后两个会议无缝衔接，所以用 >= 是默认做法。一旦满足了条件，这个活动就会被选上，并且把 last_end 更新为它的结束时间，继续往后看。如果当前活动开始时间早于 last_end，说明它和已经选过的活动有重叠，直接跳过，不更新 last_end。

2.4 完整可运行的 C 语言程序

把前面的部分拼起来，就是下面这段完整的代码。它支持从标准输入读入 n 和 n 行活动，输出每次选中的活动，最后输出最多能选几个活动。

#include <stdio.h> #include <stdlib.h> typedef struct { int start; int end; } Activity; int cmp(const void *a, const void *b) { const Activity *x = (const Activity *)a; const Activity *y = (const Activity *)b; if (x->end != y->end) { return (x->end > y->end) - (x->end < y->end); } return (x->start > y->start) - (x->start < y->start); } int main() { int n; if (scanf("%d", &n) != 1) { return 1; } Activity activities[1005]; for (int i = 0; i < n; i++) { scanf("%d%d", &activities[i].start, &activities[i].end); } qsort(activities, n, sizeof(Activity), cmp); int ans = 0; int last_end = -1; for (int i = 0; i < n; i++) { if (activities[i].start >= last_end) { printf("选中活动: [%d, %d]\n", activities[i].start, activities[i].end); ans++; last_end = activities[i].end; } } printf("%d\n", ans); return 0; }

我用 scanf 返回值做了最简单的错误处理，防止输入不是整数时程序继续空转。对于 OJ 题，scanf 返回 1 是正常的；如果输入文件为空，直接返回 1 退出更安全。代码里的输出语句主要是为了演示，实际 OJ 题通常只要求输出 ans，所以提交前可以把 printf 那行删掉。

用上一节那 5 个活动测试：

5 1 3 2 5 3 5 0 7 5 8

排序后依次是本开始于 0 到 7 的活动、1 到 3、2 到 5、3 到 5、5 到 8。程序运行结果会先选 [1, 3]，再选 [3, 5]，最后选 [5, 8]，最终 ans = 3，和预期一致。因为 [0, 7] 和 [1, 3] 重叠，[2, 5] 和已选的 [1, 3] 在 2 到 3 重叠，都被跳过。

3. 动手测试与调试技巧记录

3.1 边界条件和典型用例

只拿一两个常规用例测完就提交，很容易在边界条件上翻车。我刷题时有一个习惯：先测普通正确性，再专门测边界。表里是几个我常用的测试场景：

最后一行很值得注意。如果题目里开始时间可能是负数，而你把 last_end 初始化为 0，那么 [-3, -1] 这个活动会被错误跳过。所以我在代码里用 -1 作为初始值，只适用于非负时间；更稳妥的做法是初始化为一个明显小于所有可能取值的大负数，比如 -1e9，或者干脆用 INT_MIN。养成这种“根据数据范围设计初始值”的意识，以后写其他贪心题会少踩很多坑。

3.2 我踩过的坑和排查方法

第一次写这道题时，我把开始时间和结束时间分开成了两个数组，然后直接用 qsort 对 end 数组排序。结果活动虽然按结束时间排好了，但 start 数组还是原来的顺序，输出完全错乱。这个问题在 C 语言里非常典型，因为“排序引发数组关联丢失”是新人最容易犯的错误。用结构体之后就不会再犯。

另一个容易出问题的点是比较函数。忘记把 const void * 转回 Activity *，编译直接报错；转回之后如果返回的是 x->end - y->end，在极端数据下可能溢出。我建议你写下 cmp 函数后，先打印排序结果确认一遍。调试方法很简单，排序后临时加一个循环：

for (int i = 0; i < n; i++) { printf("sorted: [%d, %d]\n", activities[i].start, activities[i].end); }

看到排序结果符合预期，再删掉这段代码。很多“答案错误”的问题，都不是贪心策略不对，而是排序根本没排对。还有一次我把判断条件写成了 activities[i].end < last_end，完全弄反了。贪心逻辑应该是“当前活动开始时间不能早于 last_end”，而不是“结束时间小于 last_end”。如果遇到输出数量明显偏多，多半就是这种条件写反了。

3.3 用什么环境跑 C 代码更顺手

如果你只是刷活动选择这类短代码题，用在线 OJ 的编辑框直接提交就行。但如果你想在自己电脑上反复测试、加打印调试，我建议配置一个轻量的 C 语言环境。我自己用的是 VS Code 加 MinGW-w64，因为它的启动速度快，写单文件调试挺方便。配置思路不复杂：装好 MinGW 后，在 VS Code 里装 C/C++ 扩展，再配置 .vscode 下的 tasks.json 和 launch.json 让 F5 能编译调试。第一次配置确实有点繁琐，但只要跑通一次，后面写任何 C 程序都很舒服。

如果一个环境配到一半卡住了，我的备选方案是先用 Dev-C++ 或者 Code::Blocks 顶着，它们开箱即用，适合把注意力集中在算法本身。说实话，配置环境是工具层面的问题，不要让它消磨掉刷题的热情。另外，如果你习惯用文件输入测试，可以在 main 开头加一句：

freopen("test.txt", "r", stdin);

这样就能把测试数据放到 test.txt 里，每次运行程序自动读文件，免去手动一行行输入。OJ 提交前记得把这行删掉，否则读不到标准输入会超时或者 WA。

4. 从活动选择延伸到更多贪心问题

4.1 变种问题：最少教室安排

活动选择问题的一个常见变形是：现在有 n 个活动，每个都必须安排在某个时间段里，问至少需要几个教室（或者几台机器），才能让所有活动不发生重叠。这个问题和活动选择很不一样，因为活动选择追求“选尽量多”，而教室问题追求“全部安排完，但场地尽量少”。解决办法是对所有活动按开始时间排序，然后用一个最小堆维护每个教室当前的结束时间；每次来一个新活动，如果最早空闲的教室能接住它，就复用这个教室，否则新开一个教室。这里用到了优先队列，是活动选择问题往后延伸的自然一步。

乍一看，很多人会以为“最多重叠的活动数”就是最少教室数，这个结论对连续区间是对的，但实现时不能简单套用活动选择的贪心代码。从这道变种题能看出来，同样一组区间，不同的优化目标对应不同的解法，绝不能死记硬背。

4.2 为什么 0-1 背包问题不能直接用贪心

学贪心的时候，背包问题是绕不开的对比对象。分数背包允许你取一件物品的一部分，这时候按“单位重量价值”从高到低贪心装进去，就是最优解。但 0-1 背包每件物品只能整件拿或不拿，贪心就失效了。举个例子：背包容量 10，有两件物品，一件重量 6 价值 8，另一件重量 5 价值 7，按单位价值贪心会先拿第一件，剩下容量放不下第二件，总价值只有 8；但最优解是两件都不拿？不，最优解是第二件加? 容量10，第二件5，还有5放不下第一件6，只能拿第二件价值7，所以贪心拿第一件价值8反而更好？这例子不对。换一个：背包容量10，物品A重量6价值9，物品B重量5价值7，C重量5价值7，单位价值A=1.5，B=1.4，贪心拿A后装不下B或C，总价值9；最优拿B和C，总价值14。很明显贪心失败。

二分之间就差在“能不能分割”。分数背包能分割，所以每次都可以只取最划算的剩余部分，贪心的局部最优就是全局最优；0-1 背包一旦选了一个物品，就消耗了全部容量，必须考虑组合问题，局部单位价值高不代表最后总价值高。活动选择问题能使用贪心，本质上是它的结构比 0-1 背包更简单：每个活动只占用连续的一段区间，你选完一个后，剩下的问题规模是确定的，不会像背包那样产生两个不相交的子问题。

4.3 验证贪心思路的实用套路

在真实刷题和面试里，怎样马上判断一个题能不能用贪心？我的做法是三步走。第一步，先自己想一个看似合理的局部策略，比如“选择结束时间最早”。第二步，疯狂找反例，试图推翻这个策略。如果怎么都找不到反例，再去尝试证明，或者写一个小数据暴力搜索程序来对拍。第三步，如果对拍通过，心里基本就有底了。暴力对拍在比赛里很有用：写一个 O(n^n) 或 O(2^n) 的深搜版本，再写一个贪心版本，随机生成小规模数据，一把一把地喂，看输出是否一致。

活动选择问题就是非常适合用对拍来练手的题目。因为它的最优解可以用递归深搜求出，数据量小的时候，贪心和深搜结果应该完全一样。我自己的习惯是先把贪心写在 main 里，跑通之后再把它拆成函数，方便以后复用。拆成函数的好处是，当你后面写区间覆盖、会议室等问题时，可以直接拿排序和选择逻辑改一改，不用重新敲一遍。

4.4 贪心算法学习路径建议

如果你刚接触贪心，我推荐按这个顺序往下刷：活动选择问题、区间不相交问题、跳跃游戏、分发饼干、分数背包、哈夫曼编码、最小生成树的 Kruskal 算法。每道题都做完之后，你会发现它们都有一个共同特点：通过排序或某种优先级选择，把决策过程变成“每次只看当前一个最优选择”。活动选择是这个套路的起点，把它彻底吃透，后面遇到更多高级贪心题时，你能更快识别出“排序后按某个指标贪心”这一经典结构。

学习 C 语言时，我也建议把这道题当做一个完整的练习项目：用它练结构体、qsort、指针类型转换、条件判断、输入输出。当这些语法点被组合到一个实际问题里时，比单纯背语法有效得多。特别是 qsort 的比较函数，很多人学 C 一两个月了还不敢写，但刷完活动选择之后，你会觉得这不过是固定套路。

最后再分享一个我在实际调试里常用的习惯：写贪心代码时，不要急于删掉中间打印。先打印排序后的数组，再打印每一步的选择，确认无误后再注释掉。活动选择问题最核心的就两件事——排序字段对不对、重叠判断的边界条件清不清楚。这两点想清楚了，C 语言实现的复杂度并不高；真正考验功夫的是你把同样的思路迁移到别的区间类问题上时，能不能一眼看出哪些部分能贪，哪些部分必须动态规划。这道题刷明白后，你会对自己说一句：原来贪心就是“把每一步都走踏实，路自然就宽了”。