活动选择问题简介

活动选择问题（Activity Selection Problem） 是贪心算法中的一个经典问题，属于调度问题的范畴。其核心目标是从一系列竞争同一资源（如时间、场地等）的活动中，选择一个最大兼容活动子集，使得这些活动能够在不冲突的情况下进行。

问题描述

给定一组活动 S={a1,a2,...,an}S = \{a_1, a_2, ..., a_n\}S={a1​,a2​,...,an​}，每个活动 $a_i$ 都有一个开始时间 $s_i$ 和结束时间 $f_i$（假设 $f_i>s_i$）。活动 $a_i$ 和 $a_j$ 是兼容的（即不冲突），如果它们的执行时间不重叠，即满足 $s_i\ge f_j$ 或 $s_j\ge f_i$。问题的目标是找到一个最大的相互兼容的活动子集。

具体背景示例

背景：会议室安排问题。假设你是一家公司的行政主管，负责管理公司的会议室。今天有多个团队申请使用会议室，每个团队都提交了他们的会议开始和结束时间。由于会议室只有一个，你需要安排尽可能多的会议，且这些会议的时间不能重叠。如何选择会议才能最大化会议室的使用效率？

具体数据
假设有以下会议申请（按结束时间升序排列）：

会议编号	开始时间 $s_i$	结束时间 $f_i$
1	1	3
2	2	5
3	3	6
4	5	7
5	8	9
6	5	9

解决步骤（贪心算法）：

1. 排序：首先按结束时间从早到晚排序（已排序）。
2. 选择第一个活动：选择最早结束的会议（会议1：1-3），这样可以为后续会议留下更多时间。
3. 排除冲突：跳过与已选会议时间重叠的会议（即开始时间 < 已选会议的结束时间）：
   • 会议2：开始时间2 < 3（冲突，跳过）。
   • 会议3：开始时间3 = 3（不冲突，但通常认为需要严格大于，跳过）。
4. 选择下一个活动：下一个不冲突的会议是会议4（5-7）。
   • 会议5：开始时间8 > 7（不冲突）。
   • 会议6：开始时间5 < 7（冲突，跳过）。
5. 选择会议5（8-9）。
6. 结束：没有更多会议可选。

最终安排：

• 会议1（1-3）
• 会议4（5-7）
• 会议5（8-9）

这是一个最大兼容活动子集，共3个会议。

贪心选择正确性

贪心算法的正确性基于以下性质：

• 每次选择最早结束的活动，可以为剩余活动留下尽可能多的时间。
• 该问题具有贪心选择性质和最优子结构性质。

伪代码

Activity-Selection(S, f):
    Sort S by finish time in ascending order
    A = {a1}  // Select the first activity
    k = 1     // Index of last selected activity
    for m = 2 to n:
        if s_m >= f_k:  // No overlap
            A = A ∪ {a_m}
            k = m
    return A

总结

活动选择问题的核心是通过贪心策略（每次选最早结束的活动）高效地找到最大兼容子集。在会议室安排、课程调度、电视节目排期等实际场景中都有广泛应用。

贪心算法原理&应用

贪心算法是一种在每一步选择当前最优解，从而希望最终得到全局最优解的算法策略。它的核心思想是局部最优导致全局最优，适用于具有贪心选择性质和最优子结构的问题。

(1) 贪心选择性质（Greedy Choice Property）

• 当前的最优选择能导致全局最优解。
• 即：不需要考虑子问题的解，只需做出局部最优选择。
• 示例：活动选择问题中，每次选最早结束的活动，最终能得到最大兼容子集。

(2) 最优子结构（Optimal Substructure）

• 问题的最优解包含其子问题的最优解。
• 即：全局最优解可以通过局部最优解递推得到。
• 示例：最短路径问题中，从A到C的最短路径 = A→B的最短路径 + B→C的最短路径。

贪心算法的经典应用

(1) 活动选择问题（Activity Selection）

• 目标：选最多不重叠的活动。
• 贪心策略：按结束时间排序，每次选最早结束且不冲突的活动。
• 时间复杂度：O(n log n)（排序占主导）。

(2) 霍夫曼编码（Huffman Coding）

• 目标：用最短二进制编码压缩数据（高频字符用短码）。
• 贪心策略：每次合并频率最小的两个节点。
• 时间复杂度：O(n log n)。

(3) Dijkstra算法（单源最短路径）

• 目标：找到图中某点到其他点的最短路径。
• 贪心策略：每次选择当前距离起点最近的未访问节点。
• 时间复杂度：O(V²)（朴素实现）或O(E + V log V)（优先队列优化）。

(4) 最小生成树（Prim/Kruskal算法）

• 目标：用最小总边权连接所有节点。
• 贪心策略：
  • Prim：每次选连接已选集合的最小边。
  • Kruskal：每次选全局最小且不形成环的边。
• 时间复杂度：O(E log V)。

贪心算法的局限性

(1) 不保证全局最优
贪心算法可能陷入局部最优，例如：

• 背包问题：如果按价值密度（价值/重量）贪心选择，可能无法得到最优解。
• 旅行商问题（TSP）：贪心选择的路径可能比全局最优解长得多。

(2) 依赖问题性质
只有满足贪心选择性质和最优子结构的问题才能用贪心算法正确求解。

6. 如何证明贪心算法的正确性？

贪心算法的正确性通常通过以下方法证明：

1. 贪心选择性质：证明每一步的贪心选择一定包含在某个最优解中。
2. 数学归纳法：假设前k步的选择是最优的，证明第k+1步的选择仍能保持最优性。

示例（活动选择问题）：

• 贪心选择：选最早结束的活动 a₁。
• 证明：假设存在一个最优解不包含 a₁，则可以用 a₁ 替换该解中的第一个活动，仍得到兼容解，且活动数不变。因此 a₁ 一定在某个最优解中。