活动选择问题一文详解

在项目管理/任务调度等实际场景中，如何在有限的时间资源下，完成尽可能多的任务是一个关键问题，活动选择问题（Activity Selection Problem）正是对这类场景的抽象建模，通过合理选择活动安排，实现资源利用的最大化。本文我将探讨活动选择问题的问题描述、贪心求解策略、多语言代码实现、复杂度分析等方面，帮你全面掌握这一经典算法问题。

一、活动选择问题描述

1.1 问题定义

假设有一系列活动集合 S = { a 1 , a 2 , ⋯ , a n } S = \{a_1, a_2, \cdots, a_n\} S={a1​,a2​,⋯,an​}，每个活动$a_i$都有一个开始时间$s_i$和结束时间$f_i$，且$0\le s_i<f_i<\infty$ 。如果两个活动$a_i$和$a_j$的时间区间没有重叠（即$f_i\le s_j$ 或$f_j\le s_i$），则称这两个活动是兼容的。活动选择问题的目标是从给定的活动集合中，选择出一个最大的兼容活动子集，使得该子集中的活动数量最多。

1.2 示例说明

例如，给定以下活动集合：

活动	开始时间 $s_i$	结束时间 $f_i$
$a_1$	1	4
$a_2$	3	5
$a_3$	0	6
$a_4$	5	7
$a_5$	3	8
$a_6$	5	9
$a_7$	6	10
$a_8$	8	11
$a_9$	8	12
$a_{10}$	2	13
$a_{11}$	12	14

在这个例子中，最大兼容活动子集为 { a 1 , a 4 , a 8 , a 11 } \{a_1, a_4, a_8, a_{11}\} {a1​,a4​,a8​,a11​}，共包含 4 个活动。

二、贪心算法求解策略

2.1 贪心思想

活动选择问题可以通过贪心算法高效求解。贪心算法的核心思想是在每一步选择中，都做出当前状态下看似最优的选择，希望通过局部最优选择最终得到全局最优解。对于活动选择问题，贪心策略是优先选择最早结束的活动。直观理解是，选择最早结束的活动，能够为后续活动腾出更多的时间，从而有更大的机会选择更多的活动。

2.2 策略证明

我们可以通过反证法证明选择最早结束的活动能得到全局最优解。假设存在一个最优解$A$，其第一个活动不是最早结束的活动，设最早结束的活动为$a_m$。如果将$A$中的第一个活动替换为$a_m$，由于$a_m$结束时间最早，那么替换后得到的活动集合$A^{\prime }$仍然是兼容的，且活动数量不会减少。因此，选择最早结束的活动不会比其他选择更差，该贪心策略是正确的。

2.3 算法步骤

1. 对活动按结束时间排序：将所有活动按照结束时间$f_i$从小到大进行排序。排序后，最早结束的活动将排在集合的前面。

2. 初始化选择集合：选择排序后第一个活动加入结果集合，并记录该活动的结束时间。

3. 遍历剩余活动：从第二个活动开始依次遍历，对于每个活动，如果其开始时间大于等于上一个已选择活动的结束时间，则将该活动加入结果集合，并更新当前已选择活动的结束时间。

4. 返回结果：遍历结束后，得到的结果集合即为最大兼容活动子集。

三、代码实现

3.1 Python 实现

def activity_selection(activities):"""使用贪心算法解决活动选择问题:param activities: 活动列表，每个元素为 (开始时间, 结束时间) 元组:return: 最大兼容活动子集"""activities.sort(key=lambda x: x[1])  # 按结束时间排序selected_activities = [activities[0]]last_finish_time = activities[0][1]for activity in activities[1:]:start_time, finish_time = activityif start_time >= last_finish_time:selected_activities.append(activity)last_finish_time = finish_timereturn selected_activities# 示例活动集合
activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 13), (12, 14)]
result = activity_selection(activities)
print("最大兼容活动子集:", result)

3.2 C++ 实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;// 定义活动结构体
struct Activity {int start;int finish;
};// 比较函数，用于按结束时间排序
bool compare(const Activity& a, const Activity& b) {return a.finish < b.finish;
}// 活动选择函数
vector<Activity> activitySelection(vector<Activity>& activities) {sort(activities.begin(), activities.end(), compare);vector<Activity> selected_activities;selected_activities.push_back(activities[0]);int last_finish_time = activities[0].finish;for (size_t i = 1; i < activities.size(); i++) {if (activities[i].start >= last_finish_time) {selected_activities.push_back(activities[i]);last_finish_time = activities[i].finish;}}return selected_activities;
}int main() {vector<Activity> activities = {{1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 8}, {5, 9}, {6, 10}, {8, 11}, {8, 12}, {2, 13}, {12, 14}};vector<Activity> result = activitySelection(activities);cout << "最大兼容活动子集: ";for (const auto& activity : result) {cout << "(" << activity.start << ", " << activity.finish << ") ";}cout << endl;return 0;
}

3.3 Java 实现

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;class Activity {int start;int finish;public Activity(int start, int finish) {this.start = start;this.finish = finish;}
}public class ActivitySelection {public static List<Activity> activitySelection(Activity[] activities) {Arrays.sort(activities, Comparator.comparingInt(a -> a.finish));List<Activity> selectedActivities = new ArrayList<>();selectedActivities.add(activities[0]);int lastFinishTime = activities[0].finish;for (int i = 1; i < activities.length; i++) {if (activities[i].start >= lastFinishTime) {selectedActivities.add(activities[i]);lastFinishTime = activities[i].finish;}}return selectedActivities;}public static void main(String[] args) {Activity[] activities = {new Activity(1, 4), new Activity(3, 5), new Activity(0, 6), new Activity(5, 7),new Activity(3, 8), new Activity(5, 9), new Activity(6, 10), new Activity(8, 11),new Activity(8, 12), new Activity(2, 13), new Activity(12, 14)};List<Activity> result = activitySelection(activities);System.out.print("最大兼容活动子集: ");for (Activity activity : result) {System.out.print("(" + activity.start + ", " + activity.finish + ") ");}}
}

四、复杂度分析

4.1 时间复杂度

活动选择问题的时间复杂度主要由两部分组成：

• 排序时间：对活动按结束时间排序，通常使用比较排序算法（如快速排序、归并排序），时间复杂度为$O(n\log n)$，其中$n$是活动的数量。

• 遍历时间：遍历排序后的活动列表，时间复杂度为$O(n)$。

因此，整体时间复杂度为$O(n\log n+n)=O(n\log n)$，排序操作是时间复杂度的主要影响因素。

4.2 空间复杂度

算法的空间复杂度主要取决于存储活动集合和结果集合所需的空间。在最坏情况下，需要存储所有活动，空间复杂度为$O(n)$。此外，排序操作可能需要额外的辅助空间（如归并排序），但在使用原地排序算法（如快速排序）时，空间复杂度可以优化到$O(1)$。因此，总体空间复杂度为$O(n)$ 。

五、应用拓展

5.1 资源分配

在资源分配场景中，如会议室安排、设备调度等，都可以将其抽象为活动选择问题。例如，有多个会议需要使用同一间会议室，每个会议都有开始时间和结束时间，通过活动选择算法可以确定最多能安排多少个会议，实现会议室资源的高效利用。

5.2 任务调度优化

在多任务处理系统中，当多个任务对同一资源（如 CPU 核心、内存等）有使用需求时，可将任务视为活动，任务的开始和结束时间对应资源占用的时间段。利用活动选择算法，可以选择出能够在给定时间段内执行的最大任务集合，提高系统的任务处理效率。

5.3 拓展问题

活动选择问题还有许多拓展变体，例如：

• 加权活动选择问题：每个活动增加一个权重（如收益、重要程度等），目标是选择一个兼容活动子集，使得子集的总权重最大。这种情况下，贪心算法不再适用，通常需要使用动态规划算法求解。

• 多个资源的活动选择问题：当存在多个资源时，每个活动需要占用一个或多个资源，且资源在不同时间的可用状态不同，此时问题的复杂度大幅增加，需要更复杂的算法进行处理。

总结

活动选择问题作为贪心算法的经典应用，通过优先选择最早结束的活动这一简单而有效的贪心策略，能够快速找到最大兼容活动子集。

That’s all, thanks for reading!
觉得有用就点个赞、收进收藏夹吧！关注我，获取更多干货～