C++实现的活动安排问题
活动安排问题
活动安排问题是贪心算法的经典应用之一，旨在从一组活动中选择最多数量的活动，使得所选活动之间不存在时间上的重叠。
问题描述
- 输入: 一组活动，每个活动有一个开始时间和一个结束时间。
- 输出: 能够执行的最大数量的互不重叠的活动集合。
代码实现
#include <iostream>
#include <vector>
#include <algorithm>using namespace std;// 活动的结构体
struct Activity {int start;int finish;
};// 比较函数，用于按活动的结束时间进行排序
bool activityCompare(Activity a1, Activity a2) {return a1.finish < a2.finish;
}// 贪心算法实现活动选择问题
void activitySelection(vector<Activity> &activities) {// 对活动进行排序sort(activities.begin(), activities.end(), activityCompare);cout << "Selected activities are:\n";// 第一个活动总是被选择int i = 0;cout << "(" << activities[i].start << ", " << activities[i].finish << ")\n";// 选择剩余的活动for (int j = 1; j < activities.size(); j++) {// 如果活动j的开始时间不早于活动i的结束时间，则选择活动jif (activities[j].start >= activities[i].finish) {cout << "(" << activities[j].start << ", " << activities[j].finish << ")\n";i = j; // 更新上一个选择的活动}}
}int main() {int n;cout << "Enter the number of activities: ";cin >> n;vector<Activity> activities(n);cout << "Enter start and finish times of activities:\n";for (int i = 0; i < n; i++) {cin >> activities[i].start >> activities[i].finish;}activitySelection(activities);return 0;
}
思路分析
结构体设计
// Activity结构体包含两个成员变量：
// start表示活动的开始时间，finish表示活动的结束时间。
// 通过这种结构体，活动信息可以方便地存储和处理。
struct Activity {int start;int finish;
};
活动排序
// 在activitySelection()函数中，首先根据活动的结束时间进行升序排序。
// 这一步是关键，因为活动的结束时间越早，剩余时间就越多，从而可能安排更多的活动。
// 这一操作的时间复杂度为O(n log n)。
bool activityCompare(Activity a1, Activity a2) {return a1.finish < a2.finish;
}
贪心选择策略
// 在排序后的活动列表中，依次选择每个活动。
// 如果该活动的开始时间不早于上一个选择活动的结束时间，则将其加入结果集合。
// 这样保证了所选择的活动之间没有时间上的重叠，且数量最多。
// 该步骤的时间复杂度为O(n)。
void activitySelection(vector<Activity> &activities) {sort(activities.begin(), activities.end(), activityCompare);cout << "Selected activities are:\n";int i = 0;cout << "(" << activities[i].start << ", " << activities[i].finish << ")\n";for (int j = 1; j < activities.size(); j++) {if (activities[j].start >= activities[i].finish) {cout << "(" << activities[j].start << ", " << activities[j].finish << ")\n";i = j;}}
}
输出结果
// 最终输出所有选择的活动。
// 每次输出的活动都满足互不重叠的条件，从而实现了最大化活动数量的目标。
cout << "Selected activities are:\n";
for (int j = 1; j < activities.size(); j++) {if (activities[j].start >= activities[i].finish) {cout << "(" << activities[j].start << ", " << activities[j].finish << ")\n";i = j;}
}