第64课：活动选择问题

所属模块：贪心算法
难度：Intermediate
标签：activity, interval, earliest-finish
上一课：贪心算法入门
下一课：分数背包

1. 学习目标

通过本节课的学习，你将能够：

• 理解活动选择问题的定义及其在资源调度中的应用场景。
• 掌握使用贪心算法解决活动选择问题的核心策略：最早结束时间优先。
• 实现一个贪心算法来高效地选择最大数量的兼容活动。
• 分析该贪心算法的时间复杂度和正确性。

2. 核心概念

活动选择问题描述如下：你有一个集合 S = {a₁, a₂, ..., aₙ}，其中每个活动 aᵢ 都有一个开始时间 sᵢ 和一个结束时间 fᵢ（其中 sᵢ < fᵢ）。如果两个活动的时间区间不重叠（即一个活动的结束时间不晚于另一个活动的开始时间，fᵢ <= sⱼ 或 fⱼ <= sᵢ），则称这两个活动是兼容的。

目标：在给定活动集合中，找到一个最大数量的两两兼容的活动子集。

为什么贪心？ 这个问题满足贪心选择性质：局部最优解（当前选择）能导向全局最优解（最大兼容集合）。我们的贪心策略是：总是选择结束时间最早的、且与已选活动兼容的活动。

直觉：一个活动结束得越早，它留给后续活动的时间空间就越多，因此我们更有可能安排更多活动。这就像安排会议室：你总是想尽快结束当前会议，以便尽早开始下一场。

3. 代码示例

我们将实现一个函数 activity_selection，它接受活动列表并返回最大兼容活动集合。

def activity_selection(activities):
    """
    使用贪心算法求解活动选择问题。
    贪心策略：按活动结束时间升序排序，依次选择与已选活动兼容的活动。
    
    参数:
        activities (list of tuple): 每个活动表示为 (开始时间, 结束时间) 的元组。
        
    返回:
        list of tuple: 选出的最大兼容活动集合。
    """
    # 步骤1：按活动结束时间进行升序排序。这是贪心策略的核心。
    sorted_activities = sorted(activities, key=lambda x: x[1])
    
    selected_activities = []  # 存储被选中的活动
    last_finish_time = 0      # 记录上一个被选中活动的结束时间
    
    # 步骤2：遍历排序后的活动列表
    for activity in sorted_activities:
        start_time, finish_time = activity
        # 步骤3：如果当前活动的开始时间不早于上一个活动的结束时间，则它是兼容的
        if start_time >= last_finish_time:
            selected_activities.append(activity)
            last_finish_time = finish_time  # 更新最后结束时间
    
    return selected_activities

# 测试用例
if __name__ == "__main__":
    # 定义一组活动：(开始时间, 结束时间)
    activities = [
        (1, 4), (3, 5), (0, 6), (5, 7),
        (3, 9), (5, 9), (6, 10), (8, 11),
        (8, 12), (2, 14), (12, 16)
    ]
    
    result = activity_selection(activities)
    print(f"选择的最大兼容活动集合为: {result}")
    print(f"共选择了 {len(result)} 个活动。")
    
    # 预期输出（顺序可能不同，但数量一致）：
    # 选择了4个活动，例如：(1, 4), (5, 7), (8, 11), (12, 16)

代码解释：

1. 排序：首先对活动按结束时间升序排序。这是算法的关键，确保我们总是优先考虑最早结束的活动。
2. 初始化：selected_activities 存放结果，last_finish_time 初始化为0（表示在第一个活动开始前没有已占用的时间）。
3. 贪心选择：遍历排序后的列表。对于每个活动，如果其开始时间 ≥ last_finish_time，说明它与之前选中的所有活动都兼容，就将其加入结果，并更新 last_finish_time。

4. 实践练习

练习1（基础）：给定活动 [(0, 3), (1, 5), (2, 4), (4, 7), (6, 9), (8, 10)]，使用上述算法找出最大兼容活动集合，并输出数量。

练习2（进阶）：修改代码，使其不仅能返回活动集合，还能返回所选活动在原始列表中的索引（例如，返回 [0, 3, 5] 表示选择了原始列表中的第1、4、6个活动）。

练习3（思考）：假设我们改变贪心策略，改为选择开始时间最早的活动，这个策略是否总能得到最大兼容活动集合？请给出一个反例。

5. 常见错误

1. 排序依据错误：最常见的错误是按活动的开始时间排序，而不是结束时间。按开始时间排序会导致算法过早选择那些开始虽早但持续时间很长的活动，从而阻塞了更多短活动的安排。
2. 兼容性判断错误：判断兼容时，条件应为 当前活动开始时间 >= 上一个活动结束时间。注意是 >=，而不是 >。如果当前活动的开始时间恰好等于上一个活动的结束时间，它们仍然是兼容的（可以背靠背安排）。
3. 忽略预处理：活动列表可能未排序。必须先按结束时间排序，否则遍历顺序错误会导致错误结果。
4. 误解“最大”：目标是找到数量最多的活动集合，而不是总时长最长。贪心策略正是为了这个目标设计的。

6. 小结

• 问题本质：活动选择问题是一个典型的区间调度问题，目标是找出最多不重叠的区间。
• 贪心策略：最早结束时间优先（Earliest-Finish-Time-First）。
• 算法步骤：
  1. 将活动按结束时间升序排序。
  2. 选择第一个（结束最早的）活动。
  3. 依次遍历剩余活动，选择那些开始时间 ≥ 最后一个被选中活动的结束时间的活动。
• 正确性：该贪心算法总能找到一个最优解。证明思路：通过交换论证，可以证明存在一个包含第一个结束活动（即贪心选择的活动）的最优解。
• 时间复杂度：O(n log n)，主要由排序步骤决定。遍历步骤为 O(n)。

下一节课，我们将学习另一个经典的贪心问题——分数背包问题，看看如何用贪心思想处理可以分割的物品。