活动选择问题

活动选择问题（Activity Selection Problem）是贪心算法中的经典问题之一，旨在从一组竞争同一资源的活动中选出最大兼容子集（即不重叠的活动集合）。该问题广泛应用于调度优化领域，如会议安排、课程表制定等场景。

问题描述

给定一组活动 $S=\{a_1,a_2,\dots ,a_n\}$，每个活动 $a_i$ 有开始时间 $s_i$ 和结束时间 $f_i$（假设 $f_i>s_i$）。若两个活动 $a_i$ 和 $a_j$ 满足 $[s_i,f_i)\cap [s_j,f_j)=\mathrm{\varnothing }$，则称它们是兼容的。目标是找到最大的兼容活动子集。

示例输入

假设有以下活动集合（已按结束时间升序排列）：

活动列表

活动	开始时间	结束时间
a₁	1	3
a₂	2	5
a₃	4	7
a₄	6	9
a₅	8	10

贪心算法解法

贪心算法的核心思想是：**每次选择结束时间最早的活动**，以留出更多时间给剩余活动。步骤如下： 1. 将活动按结束时间升序排序。 2. 选择第一个活动，并记录其结束时间。 3. 遍历后续活动，若其开始时间 ≥ 当前结束时间，则选择该活动并更新结束时间。

伪代码

  
def activity_selection(start, finish):  
    selected = []  
    n = len(start)  
    i = 0  
    selected.append(i)  # 选择第一个活动  
    for j in range(1, n):  
        if start[j] >= finish[i]:  
            selected.append(j)  
            i = j  
    return selected

代码示例

以下为Python实现及输出：

  
start = [1, 2, 4, 6, 8]  
finish = [3, 5, 7, 9, 10]  
selected = activity_selection(start, finish)  
print("Selected activities:", selected)  # 输出: [0, 2, 4]

• • 输出解释**：

- 选择活动 a₁（时间 1–3），结束时间为 3。 - 跳过 a₂（与 a₁ 重叠），选择 a₃（4–7）。 - 跳过 a₄（与 a₃ 重叠），选择 a₅（8–10）。

可视化流程

gantt title 活动选择过程 dateFormat HH axisFormat %H section 选择 a₁ : 1, 3 a₃ : 4, 7 a₅ : 8, 10 section 跳过 a₂ : 2, 5 a₄ : 6, 9

正确性证明

贪心选择性质：每次选择局部最优解（最早结束的活动）能导向全局最优解。 - 假设存在一个最优解不包含最早结束的活动 $a_1$，则可用 $a_1$ 替换该解中的第一个活动，仍保持兼容性且解大小不变。

实际应用

1. **会议室调度**：在一间会议室中安排最多会议。 2. **CPU任务调度**：优化任务执行顺序以最大化吞吐量。 3. **教育课程表**：避免课程时间冲突。

变种与扩展

- **加权活动选择**：每个活动有权重，目标是最大化总权重（需用动态规划解决）。 - **资源约束**：多个资源（如多间会议室）时的扩展问题。

练习

尝试对以下活动集合求解最大兼容子集：

活动	开始时间	结束时间
A	5	9
B	1	2
C	3	4
D	0	6

• • 答案**：选择 B（1–2）和 C（3–4）。