活动选择问题

有若干活动 $a_i=[s_i,f_i)$ ，同一资源一次只能执行一个活动。目标是在所有活动中选择数量最多的一组，使任意两个活动不重叠。

1. 正确的贪心选择

按结束时间 $f_i$ 从小到大排序，每次选择第一个与已选活动兼容的活动：

sort by finish time ascending
lastFinish = -infinity
for activity in order:
    if activity.start >= lastFinish:
        select activity
        lastFinish = activity.finish

排序耗时 $O(n\log n)$ ；若输入已按结束时间排好，扫描只需 $O(n)$ 。

2. 为什么“最早结束”有用

当前选择结束得越早，为后续活动留下的时间越多。交换论证如下：

设 $a_g$ 是所有候选活动中结束最早的。任取一个最优方案，其第一个活动为 $a_o$ 。因为

f_g\le f_o,

用 $a_g$ 替换 $a_o$ 后，原来能接在 $a_o$ 后面的活动仍能接在 $a_g$ 后面，活动数量不减少。因此至少存在一个最优解以 $a_g$ 开头。

选定它后，只需在开始时间不早于 $f_g$ 的活动中解决同类子问题。

3. 容易混淆的其他策略

以下直觉都不保证正确：

最早开始：可能选中一个持续很久的活动；
持续时间最短：短活动的位置可能正好挡住左右两边两个活动；
冲突数最少：局部冲突少不代表给后续留下最大空间；
当前空档最小：没有稳定的交换性质。

贪心题不能只凭直觉，要能给出交换论证或其他严格证明。

4. 区间边界

把活动写成半开区间 $[s_i,f_i)$ 时， $s_j=f_i$ 代表两活动兼容。若题目把端点也视为占用，就要使用严格不等式。实现前必须先确认语义。

5. 递归与迭代形式

递归做法选最早结束活动后，递归处理其右侧兼容集合；迭代做法用一个 lastFinish 完成同样逻辑。迭代更简单，证明完全一致。

也可以从右向左，反复选择开始时间最晚的兼容活动。这是时间反转后的等价贪心。

6. 加权活动选择不能照搬

若每个活动有价值 $v_i$ ，目标改为总价值最大，最早结束贪心会失败。此时按结束时间排序，并定义前驱

p(i)=\max\{j<i:f_j\le s_i\},

使用动态规划：

OPT(i)=\max\{OPT(i-1),\ v_i+OPT(p(i))\}.

这就是“无权最大数量”与“加权最大价值”的分界。

7. 与区间调度的关系

单机器区间调度、会议室安排中的“最多安排多少场”都属于活动选择。若问题改成“所有活动至少需要几间会议室”，目标不同，应按开始时间扫描并维护结束时间最早的会议室，而不是丢弃冲突活动。