CSCI3160 L03 活动选择与交换论证

课程：CSCI3160 Design and Analysis of Algorithms 本讲：L03 活动选择与交换论证 · 原件 L03-Greedy-01-Activity-Selection-未核.pdf（本地课件） p.1–11 定位：手工执行最早结束贪心，并用交换论证解释每一步为什么可以保留全局最优解。

p.1 标题页。

局部选择需要全局证明（p.2–3）【新】

p.2 The nontrivial part is to prove (or disprove) the global optimality.

p.2 的贪心（greedy）是每步按一个局部指标直接选择；局部看着好，不自动等于最终最优。本讲真正要学的是怎样证明“选完这一步仍至少有一个最优解可走”。

题面（L03-Greedy-01-Activity-Selection-未核.pdf · Activity Selection · p.3）

p.3 Input: A set S of n intervals of the form [s, f] where s and f are integers. Output: A subset T of disjoint intervals in S with the largest size $\lvert T\rvert$ .

p.3 最大化的是活动个数，不是总时长、总收益。区间是闭区间：[1,3] 与 [3,5] 共享时刻 3，按此定义相交。兼容条件应是下一活动开始时刻严格大于前一活动结束时刻。

一个实例与贪心执行（p.4–6）

题面（同原件 · Example · p.4）

p.4 Example: Suppose $S=\{[1,9],[3,7],[6,20],[12,19],[15,17],[18,22],[21,24]\}$ . $T=\{[3,7],[15,17],[18,22]\}$ is an optimal solution, and so is $T=\{[1,9],[12,19],[21,24]\}$ .

公式按讲义重排。p.4 两个最优解都含三个活动，说明最优解不一定唯一；算法只需得到其中一个。

p.5 Add to T the interval $I\in S$ with the smallest finish time.

p.5 最先结束的活动给后面留下最多时间；选它后删除与它相交的所有候选，包括自身。p.6 把结束时刻排序并跑完整过程：

步骤	选入	本轮删除	剩余
1	[3,7]	[3,7]、[1,9]、[6,20]	[15,17]、[12,19]、[18,22]、[21,24]
2	[15,17]	[15,17]、[12,19]	[18,22]、[21,24]
3	[18,22]	[18,22]、[21,24]	空

这是 p.6 原例的逐轮表。输出大小为 3。不能只把“最早结束留下时间”当作证明；下一页解释为什么交换不会损失活动数。

补充：先用反例筛掉看起来合理的指标。 自取闭区间 [1,10]、[2,3]、[4,5]、[6,7]。按最早开始会选 [1,10]，只能得到一个；按最早结束会依次选后三个，得到三个。再取 [0,3]、[4,7]、[2,5]：第三个区间长度 3，与另两个长度相同，若“最短优先”在并列时选第三个，就只得一个，而前两个兼容可得两个。要排除并列影响，可把第三个改为 [2,4]，它严格更短却仍与两边闭区间相交。反例证明其他指标可能失败，但不是对最早结束规则的证明。

这里特别依赖活动收益都按“一项”计算。如果给第一个长活动收益 100、三个短活动各收益 1，最大数量与最大收益就选择不同解；交换论证中“换掉一项数量不变”不能自动升级为“收益不变”。

自测：证明目标应是每个最优解都含贪心首项吗？

不需要，也一般不成立。原例已经有不含 [3,7] 的最优解。足够的结论是：至少存在一个最优解含它；交换把任意最优解转成这样的一个解，后续才有继续扩展的余地。

第一次交换为什么安全（p.7–8）【新】

p.7 Claim 1: Let $I_1$ be the first interval picked by our algorithm. There must be an optimal solution containing $I_1$ .

p.7 取任意最优解 $T^{\ast}$ 。如果它已含贪心活动 $I_1$ 就结束；否则把其中结束最早的活动 $I'_1$ 换成 $I_1$ 。交换只替换一项，数量不变；唯一要证明的是仍然互不相交。

p.8 的理由是：最优解中其余每个活动 J 都开始于 $I'_1$ 结束之后；而 $I_1$ 是全体候选中结束最早的，因此不晚于 $I'_1$ 结束。于是 $f(I_1)\le f(I'_1)<s(J)$ ，新活动也不会碰到 J。结果仍是同样大小的可行解，因而仍最优。

算一遍：用 p.4 的另一最优解 {[1,9],[12,19],[21,24]}，把 [1,9] 换成 [3,7]，得到 {[3,7],[12,19],[21,24]}。第二项从 12 开始，而新第一项在 7 结束，仍兼容；数量仍为 3。

前缀归纳与终止（p.9–10）

p.9 All the intervals in $T^{\ast}\setminus\{I_1,\ldots,I_{k-1}\}$ must start strictly after the finish time of $I_{k-1}$ .

p.9 把第一次交换推广到已经选了若干项的情形。为什么最优解额外的活动不能插在贪心前缀中间？若有一个活动 J 与已选前缀不冲突且位于 $I_{j-1}$ 与 $I_j$ 之间，那么选 $I_j$ 时 J 也仍是候选，却比 $I_j$ 更早结束，这与贪心规则矛盾。第一次选择之前的空档也用同样理由排除。剩余活动只能在前缀之后。

p.9 的 Claim 2 完整含义是：已经有某个最优解包含前 k−1 个贪心活动，就能找到某个最优解包含前 k 个。这里的最优解允许随交换改变，前缀中的活动却必须全部留下。还要解释为什么最优解中能找出用于交换的剩余活动：若它只有前 k−1 项，而算法还能选第 k 项，那么这 k 项构成一个更大的可行解，便与最优性矛盾。

p.10 于是可以在剩余活动中找到结束最早的 $I'_k$ ，用本轮贪心 $I_k$ 替换；它与此前前缀兼容，且不晚于 $I'_k$ 结束，不会挡住之后的活动。归纳得到每个贪心前缀都可扩成某个最优解。算法结束后候选为空，那个最优解不可能再有额外兼容活动，所以当前解本身最优。

算一遍：承上节交换后的最优解，前缀固定 [3,7]，剩余最早结束的 [12,19] 可换为 [15,17]；第三项 [21,24] 从 21 开始，仍不冲突。再把 [21,24] 换成贪心最后选的 [18,22]，即得到算法输出的三项。

怎样实现到排序时间（p.11）

题面（同原件 · 实现问题 · p.11）

p.11 Think: How to implement the algorithm in $O(n\log n)$ time?

先按结束时刻排序，花 $O(n\log n)$ ；维护上一个选中活动的结束时刻，顺序扫描，每个候选只判断一次。开始时刻严格更大就选入，否则跳过。无须每轮真的从数组删去一批元素，反复整体搬移反而可能退化到平方时间。

将活动按 finish 非降序排序
last_finish = 负无穷
for 活动 [s,f] 按排序顺序：
  若 s > last_finish：
    输出 [s,f]
    last_finish = f

用 p.6 排序顺序扫描：选 [3,7]，跳 [1,9]，选 [15,17]，跳 [12,19] 与 [6,20]，选 [18,22]，跳 [21,24]，与逐轮删除版完全相同。

考试角度：（A 级（扫描件，视觉读取）：Final-2025T1-题目.pdf Q1(g)，考把时间方向反过来的贪心；演练见附录 A1）。

本讲核心考点

闭区间兼容要求严格晚于，不是大于等于（p.3，C 级）。
交换论证同时保持可行性和活动数量（p.7–10，C 级）。
先排序再扫描实现O(n log n)（p.11，C 级）。
反向选择最晚开始时间同样有交换证明（对应往年Q1(g)，A 级）。

附录

A1 作业/往年题演练（非讲义内容）：最晚开始的活动

题面（Final-2025T1-题目.pdf · Q1(g) · p.2；扫描件，视觉读取）

p.2 (g) (2 points) Let S be a set of intervals of the form [s,f]. We will refer to s as the “start time” of the interval. The algorithm shown in Algorithm 2 solves the activity selection problem on S optimally.

Algorithm 2: 1: procedure ACTIVITY-SEL(S) 2: T ← empty set 3: repeat 4: I ← an interval in S with the largest start time 5: add I to T 6: remove from S all the intervals that intersect with I 7: until S is empty 8: return T

结论是 True。不能因为课堂按结束时间排序就断言改按开始时间一定错误；这里选择的是最晚开始，相当于从右往左排活动。

取任意最优解中开始最晚的活动 J，以本轮开始最晚的 I 替换。最优解其余活动 K 都在 J 之前，故 $f(K)<s(J)\le s(I)$ ，所以它们与 I 仍不冲突。交换前后数量相同，存在包含 I 的最优解。删除冲突活动后，对剩余区间重复此论证，最终得到最优解。

用讲义 p.4 的实例验证：先选 [21,24]，删 [18,22]；再选 [15,17]，删 [12,19] 与 [6,20]；最后选 [3,7]，删 [1,9]。得到三项，与已知最优值一致。该实例是核对，最优性的普遍保证仍来自刚才的交换证明。

回到正文：怎样实现到排序时间（p.11）

来源与证据

本次逐页复核：2026-10-13，依据上述本地课件；保留已发布深化内容，页码指 PDF 物理页。历史考试演练保留其原有出处，本次不将旧记录冒充重新阅卷。
原件：L03-Greedy-01-Activity-Selection-未核.pdf（本地课件）；页码均为 PDF 页号。
版本记录（2026-09-17）：当时从教师官网下载并逐字节核对，与本地原件一致；此日期不是本次重新联网核验。原始学期未核，不据网页学期补猜。
既有考试证据记录（2026-09-17）：当时读取了教师官网、Midterm-2021T1-题目.pdf、Midterm-2021T1-题解.pdf、Review-Quiz-2020T2-题目.pdf、Review-Quiz-2020T2-题解.pdf、Quiz-01-2025T1-题解.pdf、Midterm-A-2025T1-缺题干-解答.pdf、Quiz-02-2025T1-缺题干-解答.pdf、Quiz-03-2025T1-缺题干-解答.pdf、Final-2021T1-题解.pdf、Final-2024T1-缺判断-题目.pdf、Final-2025T1-题目.pdf、Final-2025T1-缺题干-解答.pdf；未识别用途的 PDF：无
缺题干解答卷仅用于核对已取得的题面，不由答案反推题目。