编辑“︁活动选择问题”︁

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

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

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

{| class="wikitable"  
|+ 活动列表  
! 活动 !! 开始时间 !! 结束时间  
|-  
| a₁ || 1 || 3  
|-  
| a₂ || 2 || 5  
|-  
| a₃ || 4 || 7  
|-  
| a₄ || 6 || 9  
|-  
| a₅ || 8 || 10  
|}  

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

=== 伪代码 ===  
<syntaxhighlight lang="python">  
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  
</syntaxhighlight>  

=== 代码示例 ===  
以下为Python实现及输出：  
<syntaxhighlight lang="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]  
</syntaxhighlight>  

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

=== 可视化流程 ===  
<mermaid>  
gantt  
    title 活动选择过程  
    dateFormat  HH  
    axisFormat %H  
    section 选择  
    a₁ : 1, 3  
    a₃ : 4, 7  
    a₅ : 8, 10  
    section 跳过  
    a₂ : 2, 5  
    a₄ : 6, 9  
</mermaid>  

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

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

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

== 练习 ==  
尝试对以下活动集合求解最大兼容子集：  
{| class="wikitable"  
! 活动 !! 开始时间 !! 结束时间  
|-  
| A || 5 || 9  
|-  
| B || 1 || 2  
|-  
| C || 3 || 4  
|-  
| D || 0 || 6  
|}  
**答案**：选择 B（1–2）和 C（3–4）。  

{{贪心算法}}

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:贪心算法]]