贪心算法 - 活动选择问题 - 活动选择问题的贪心解法

贪心算法 - 活动选择问题 - 活动选择问题的贪心解法

一、引言

在日常生活和工作中，我们常常会面临这样的情况：有多个活动需要安排，但由于时间或资源的限制，无法同时进行所有活动，必须从中挑选出一部分活动，使得在有限的条件下获得最大的收益。活动选择问题就是这类问题的典型代表，而贪心算法则是解决该问题的一种高效策略。

二、活动选择问题的定义

活动选择问题描述如下：假设有一个礼堂，有 $n$ 个活动需要使用这个礼堂，每个活动 $i$ 都有一个开始时间 $s_i$ 和结束时间 $f_i$，且 $s_i < f_i$。我们的目标是在这个礼堂中安排尽可能多的活动，使得这些活动的时间区间两两不重叠。也就是说，如果选择了活动 $i$ 和活动 $j$，那么要么 $f_i \leq s_j$，要么 $f_j \leq s_i$。

示例

假设有以下 6 个活动，它们的开始时间和结束时间如下表所示：
| 活动编号 | 开始时间 ($s_i$) | 结束时间 ($f_i$) |
| —— | —— | —— |
| 1 | 1 | 4 |
| 2 | 3 | 5 |
| 3 | 0 | 6 |
| 4 | 5 | 7 |
| 5 | 3 | 9 |
| 6 | 5 | 9 |

我们需要从这些活动中选择尽可能多的不重叠活动。

三、贪心算法的基本思想

贪心算法是一种在每一步选择中都采取当前状态下最优（即最有利）的选择，从而希望最终结果也是全局最优的算法。对于活动选择问题，贪心算法的核心思想是每次都选择结束时间最早且与已选择的活动不冲突的活动。

直观地理解，选择结束时间最早的活动可以为后续活动留出更多的时间，从而有可能安排更多的活动。

四、活动选择问题的贪心解法步骤

步骤 1：对活动按结束时间进行排序

首先，将所有活动按照结束时间从小到大进行排序。这样做的目的是为了方便我们每次都能快速找到结束时间最早的活动。

对于上述示例，排序后的活动信息如下表所示：
| 活动编号 | 开始时间 ($s_i$) | 结束时间 ($f_i$) |
| —— | —— | —— |
| 1 | 1 | 4 |
| 2 | 3 | 5 |
| 4 | 5 | 7 |
| 3 | 0 | 6 |
| 5 | 3 | 9 |
| 6 | 5 | 9 |

步骤 2：选择第一个活动

由于第一个活动的结束时间最早，我们首先选择它。在上述示例中，我们选择活动 1。

步骤 3：依次选择后续活动

从第二个活动开始，依次检查每个活动的开始时间是否大于等于上一个已选择活动的结束时间。如果满足条件，则选择该活动，并更新上一个已选择活动为当前活动；否则，跳过该活动。

具体过程如下：

• 选择活动 1 后，活动 2 的开始时间 $s_2 = 3$，$3 < 4$（活动 1 的结束时间），所以不选择活动 2。
• 活动 4 的开始时间 $s_4 = 5$，$5 \geq 4$（活动 1 的结束时间），所以选择活动 4，此时上一个已选择活动变为活动 4。
• 活动 3 的开始时间 $s_3 = 0$，$0 < 7$（活动 4 的结束时间），所以不选择活动 3。
• 活动 5 的开始时间 $s_5 = 3$，$3 < 7$（活动 4 的结束时间），所以不选择活动 5。
• 活动 6 的开始时间 $s_6 = 5$，$5 < 7$（活动 4 的结束时间），所以不选择活动 6。

最终，我们选择的活动是活动 1 和活动 4，这是在这些活动中能安排的最多不重叠活动。

代码实现（Python）

def activity_selection(start, finish):
    n = len(start)
    activities = []
    # 将活动的开始时间、结束时间和编号组合在一起
    for i in range(n):
        activities.append((start[i], finish[i], i))
    # 按结束时间排序
    activities.sort(key=lambda x: x[1])
    selected_activities = []
    # 选择第一个活动
    selected_activities.append(activities[0][2])
    last_finish_time = activities[0][1]
    # 依次选择后续活动
    for i in range(1, n):
        if activities[i][0] >= last_finish_time:
            selected_activities.append(activities[i][2])
            last_finish_time = activities[i][1]
    return selected_activities
# 示例数据
start = [1, 3, 0, 5, 3, 5]
finish = [4, 5, 6, 7, 9, 9]
result = activity_selection(start, finish)
print("选择的活动编号为:", [i + 1 for i in result])

五、贪心算法的正确性证明

要证明贪心算法在活动选择问题上的正确性，我们需要证明两个方面：

1. 贪心选择性质

贪心选择性质是指问题的全局最优解可以通过一系列局部最优选择得到。在活动选择问题中，我们每次选择结束时间最早且与已选择活动不冲突的活动，这个选择是局部最优的。可以证明，存在一个全局最优解包含了这个最早结束的活动。

假设 $S$ 是活动选择问题的一个全局最优解，且 $a$ 是所有活动中结束时间最早的活动。如果 $a$ 不在 $S$ 中，我们可以用 $a$ 替换 $S$ 中任意一个活动 $b$，由于 $a$ 的结束时间最早，替换后得到的解仍然是一个可行解，且活动数量不变，所以仍然是最优解。因此，存在一个全局最优解包含了最早结束的活动，满足贪心选择性质。

2. 最优子结构性质

最优子结构性质是指问题的最优解包含了子问题的最优解。在活动选择问题中，当我们选择了一个活动 $a$ 后，剩下的问题就是在与 $a$ 不冲突的活动中选择尽可能多的活动，这是一个规模更小的活动选择子问题。可以证明，原问题的最优解包含了这个子问题的最优解。

假设我们选择了活动 $a$，并将与 $a$ 冲突的活动去掉，得到子问题 $P’$。设 $S$ 是原问题的最优解，$S’$ 是 $S$ 中除去 $a$ 后剩下的活动集合。如果 $S’$ 不是子问题 $P’$ 的最优解，那么存在一个更优的解 $S’’$ 对于子问题 $P’$，将 $a$ 加入 $S’’$ 后得到的解将比 $S$ 包含更多的活动，这与 $S$ 是原问题的最优解矛盾。因此，原问题的最优解包含了子问题的最优解，满足最优子结构性质。

六、复杂度分析

时间复杂度

排序操作的时间复杂度为 $O(n log n)$，其中 $n$ 是活动的数量。遍历活动列表的时间复杂度为 $O(n)$。因此，整个算法的时间复杂度为 $O(n log n)$。

空间复杂度

主要的空间开销是存储活动信息和选择的活动列表，空间复杂度为 $O(n)$。

七、总结

活动选择问题是一个经典的组合优化问题，贪心算法为其提供了一种简单而高效的解决方案。通过每次选择结束时间最早且与已选择活动不冲突的活动，我们可以在 $O(n log n)$ 的时间复杂度内得到最优解。贪心算法的核心在于贪心选择性质和最优子结构性质，这使得我们可以通过局部最优选择得到全局最优解。

在实际应用中，活动选择问题的贪心解法可以应用于很多场景，如会议安排、课程表编排等。通过合理运用贪心算法，我们可以在有限的资源下安排更多的活动，提高资源的利用率。