题目描述

问题背景

活动选择问题是贪心算法的经典应用场景之一。假设有若干个活动，每个活动都有独立的开始时间和结束时间，且同一时间只能进行一个活动。要求从这些活动中选择出最大数量的不重叠活动，即任意两个选中的活动，前一个活动的结束时间不晚于后一个活动的开始时间。

输入输出示例

输入（开始时间与结束时间分两行输入，空格分隔，回车结束）：
plaintext
```
1 3 0 5 8 5  // 活动开始时间
2 4 6 7 9 9  // 活动结束时间
```
输出：
plaintext
```
最大不重叠活动数量: 4
```
解释：最优选择为活动 [1,2]、[3,4]、[5,7]、[8,9]，共 4 个不重叠活动。

解题思路：贪心算法的核心逻辑

为什么选择贪心算法？

活动选择问题的最优解具有 “贪心选择性质”—— 每次选择最早结束的活动，能为后续活动预留最多的时间，从而最大化最终选择的活动数量。这一策略无需回溯，直接通过局部最优选择即可得到全局最优解。

算法步骤

数据组织：将每个活动的 “开始时间” 和 “结束时间” 组合成二维向量 vector<vector<int>>，每行代表一个活动（格式：[开始时间, 结束时间]）。
排序：按活动的结束时间升序排序（贪心策略的关键，确保优先选择早结束的活动）。
筛选不重叠活动：
- 初始选择第一个活动（最早结束的活动），记录其结束时间。
- 遍历后续活动，若当前活动的 “开始时间 ≥ 上一个选中活动的结束时间”，则选择该活动，并更新结束时间。
统计结果：记录最终选择的活动数量，即为答案。

完整 C++ 代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;/*** @brief 计算最大不重叠活动数量（贪心算法）* @param activities 二维向量，每行存储一个活动的[开始时间, 结束时间]*/
void selectMaxNonOverlappingActivities(vector<vector<int>>& activities) {// 边界处理：若没有活动，直接返回0if (activities.empty()) {cout << "最大不重叠活动数量: 0" << endl;return;}// 按活动结束时间升序排序（贪心算法核心：优先选早结束的活动）sort(activities.begin(), activities.end(), [](const vector<int>& activity1, const vector<int>& activity2) {return activity1[1] < activity2[1]; // 按结束时间从小到大排序});int activityCount = 1;                  // 至少选择第一个活动int lastActivityEndTime = activities[0][1]; // 记录上一个选中活动的结束时间// 遍历剩余活动，筛选不重叠的活动for (size_t i = 1; i < activities.size(); ++i) {// 若当前活动的开始时间 ≥ 上一个活动的结束时间，说明不重叠if (activities[i][0] >= lastActivityEndTime) {activityCount++; // 选择当前活动lastActivityEndTime = activities[i][1]; // 更新结束时间为当前活动的结束时间}}// 输出结果cout << "最大不重叠活动数量: " << activityCount << endl;
}int main() {vector<int> startTimes;  // 存储所有活动的开始时间vector<int> endTimes;    // 存储所有活动的结束时间vector<vector<int>> activities; // 存储所有活动（[开始时间, 结束时间]）int timeInput;           // 临时存储输入的时间值// 读取活动开始时间（空格分隔，回车结束）cout << "请输入所有活动的开始时间（空格分隔，回车结束）：" << endl;while (cin >> timeInput) {startTimes.push_back(timeInput);// 检测到回车符，停止读取开始时间if (cin.peek() == '\n') {cin.ignore(); // 清空输入缓冲区的换行符，避免影响后续输入break;}}// 读取活动结束时间（空格分隔，回车结束）cout << "请输入所有活动的结束时间（空格分隔，回车结束）：" << endl;while (cin >> timeInput) {endTimes.push_back(timeInput);if (cin.peek() == '\n') {break;}}// 输入合法性校验：开始时间和结束时间的数量必须一致if (startTimes.size() != endTimes.size()) {cerr << "输入错误：开始时间和结束时间的数量不匹配！" << endl;return 1; // 非0返回值表示程序异常退出}// 组合开始时间和结束时间，构建活动列表for (size_t i = 0; i < startTimes.size(); ++i) {activities.push_back({startTimes[i], endTimes[i]});}// 计算并输出最大不重叠活动数量selectMaxNonOverlappingActivities(activities);return 0;
}

代码细节解析

1. 边界处理与输入校验

空活动判断：若输入为空（无任何活动），直接输出 0，避免数组越界。
输入合法性校验：确保 “开始时间数量” 与 “结束时间数量” 一致，若不一致则提示错误并退出，避免后续逻辑异常。
输入缓冲区清理：使用 cin.ignore() 清除第一个输入后的换行符，防止换行符被第二个输入循环误读。

2. 排序逻辑（Lambda 表达式）

cpp

运行

sort(activities.begin(), activities.end(), [](const vector<int>& activity1, const vector<int>& activity2) {return activity1[1] < activity2[1];});

使用 Lambda 表达式作为排序的自定义比较函数，简洁高效。
按活动的结束时间（activity[1]）升序排序，是贪心策略的核心 —— 优先选择早结束的活动，为后续活动预留更多时间。

3. 活动筛选逻辑

初始选择第一个活动（排序后最早结束的活动），activityCount 初始化为 1。
遍历后续活动时，通过 activities[i][0] >= lastActivityEndTime 判断是否重叠：
- 若满足条件：选择该活动，activityCount 加 1，并更新 lastActivityEndTime 为当前活动的结束时间。
- 若不满足：跳过该活动，继续遍历下一个。

算法效率分析

时间复杂度	空间复杂度	说明
O(n log n)	O(n)	时间复杂度由排序操作主导（`sort` 函数的时间复杂度为 O (n log n)）；空间复杂度用于存储活动列表，为 O (n)（n 为活动数量）。

该效率是活动选择问题的最优解 —— 贪心算法无需额外的动态规划数组，在时间和空间上均优于其他解法。