活动选择问题

概述

活动选择问题是贪心算法的经典入门问题：给定 $n$ 个活动及其时间区间，选择最大的互相兼容的活动子集。该问题的贪心策略——选择最早结束的活动——具有直觉上的合理性：尽早释放资源以容纳更多活动。它是区间调度问题的核心，广泛应用于资源分配和任务调度场景。

定义

活动选择问题（Activity Selection）

输入：$n$ 个活动 $S=\{a_1,a_2,\dots ,a_n\}$，每个活动 $a_i$ 有开始时间 $s_i$ 和结束时间 $f_i$（假设已按结束时间排序：$f_1\le f_2\le \cdots \le f_n$）。

输出：$S$ 的最大兼容子集 $A$，其中兼容意味着任意两个活动不重叠（即对于 $a_i,a_j\in A$，要么 $f_i\le s_j$，要么 $f_j\le s_i$）。

贪心策略：每次选择结束时间最早且与已选活动兼容的活动。

核心性质

1. 贪心选择性质

选择结束时间最早的活动 $a_m$ 后，剩余子问题是在 $S_m=\{a_i\in S:s_i\ge f_m\}$ 中选择最大兼容子集。由 贪心选择性质 中的 Theorem 15.1 可知，$a_m$ 包含在某个最优解中。

2. 递归贪心算法

RECURSIVE-ACTIVITY-SELECTOR(s, f, k, n):
    m = k + 1
    while m <= n and s[m] < f[k]:   // 找到第一个与 a_k 兼容的活动
        m = m + 1
    if m <= n:
        A = {a_m} ∪ RECURSIVE-ACTIVITY-SELECTOR(s, f, m, n)
        return A
    else:
        return ∅

初始调用：RECURSIVE-ACTIVITY-SELECTOR(s, f, 0, n)，其中 $f[0]=0$ 表示虚拟活动的结束时间。

3. 迭代贪心算法

GREEDY-ACTIVITY-SELECTOR(s, f):
    n = s.length
    A = {a_1}                        // 选择第一个活动（最早结束的）
    k = 1
    for m = 2 to n:
        if s[m] >= f[k]:             // a_m 与 a_k 兼容
            A = A ∪ {a_m}
            k = m
    return A

迭代版本更简洁高效，避免了递归调用的开销。

4. 时间复杂度分析

阶段	时间复杂度
按结束时间排序	$O(n\log n)$
贪心选择（已排序）	$\Theta (n)$
总时间	$O(n\log n)$（未排序）或 $\Theta (n)$（已排序）

5. 为什么选择”最早结束”而不是”最早开始”

• 最早结束：正确。直觉：尽早释放资源，为后续活动留出更多空间
• 最早开始：错误。反例：一个活动从时间0开始持续100个单位，而另一个从时间1开始持续2个单位。选最早开始会错过大量后续活动
• 最短活动：错误。反例：短活动可能与多个稍长但不重叠的活动冲突
• 最少冲突：错误。反例：一个活动虽然冲突少，但可能阻塞关键时间段

应用场景

• 会议室调度：在有限会议室中安排最多的会议
• CPU任务调度：在单处理器上调度不重叠的任务
• 资源分配：在共享资源上安排最多的使用者
• LeetCode 相关题目：
  • LeetCode 435：Non-overlapping Intervals（求最少移除区间数）
  • LeetCode 253：Meeting Rooms II（求最少会议室数，变体问题）

章节扩展

• 15.1 活动选择问题 — 活动选择问题的完整求解过程
• 贪心算法 — 贪心算法完整方法论
• 贪心选择性质 — 贪心选择性质的详细说明
• 替换论证 — 证明贪心正确性的技术

参见

• 哈夫曼编码 — 另一个经典贪心问题
• 离线缓存 — 贪心算法的另一个应用
• 动态规划 — 活动选择问题的加权版本可用动态规划求解