GESP 五级 · GESP202609 C++ 五级 第 13 题

小杨要在一个教室安排尽可能多场活动，每场活动具有开始时间 start 和结束时间 end 。采用贪心算法 时，正确的选择策略是（　　）。

struct Activity {
int start;
int end;
};

区间调度最大化活动数量，贪心核心是"尽早腾出空间"。看到题先想：要选尽可能多，就得让每次选择后剩余可用时间最多。关键观察：结束越早，留给后面的时间越充裕。因此必须按结束时间升序排序，然后线性扫描——当前活动若与上一个已选活动不重叠（start ≥ last_end），就选它。其他排序（按开始时间、按时长）都无法保证全局最优，因为局部最优≠全局最优。

A 选项"最早开始"是典型陷阱，学生容易把"早开始=早结束"想当然，但早开始的活动可能持续很久，反而挤占后续空间。B 选项"最短时长"同样诱人，短活动未必早结束，可能晚收尾。C 选项"参与人数"纯属语义干扰，题干只约束时间。最阴险的是 D 选项前半句"按结束时间排序"——若排序后不检查冲突，会误选重叠活动，所以必须强调"依次选择不冲突的"。

1. 考纲定位

本题考查《GESP 五级算法设计》中的贪心策略与区间调度。命题人放这道题，就是要卡住那些"会贪心但不会选贪心策略"的考生——他们知道贪心要局部最优，却误以为局部最优是"最早开始"或"最短时长"，而非"最早结束"。

2. 解题思维

贪心选择性质要求：每一步选出的活动，必须为后续活动留下最大可能空间。空间由"结束时间"决定，而非开始时间或时长。因此排序必须按 end 升序。扫描时维护 last_end 变量，初始为负无穷。对每个活动，若 start ≥ last_end，则选它并更新 last_end = end。这样保证任意两个选中活动都不重叠，且数量最大。

反证：若存在最优解未包含最早结束的活动，把最早结束的活动换进去，不会增加冲突（因为它结束更早），数量不变，说明最早结束的活动必可被纳入最优解。