实验二：贪心算法
【实验目的】
应用贪心算法求解活动安排问题。
【实验性质】
验证性实验。
【实验要求】
活动安排问题是可以用贪心算法有效求解的很好的例子。
问题：有n个活动的集合A={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。
求解：安排尽量多项活动在该场地进行，即求A的最大相容子集。
设待安排的11个活动的开始时间和结束时间按结束时间的升序排列如下：
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| s[i] | 1 | 3 | 0 | 5 | 3 | 5 | 6 | 8 | 8 | 2 | 12 |
| f[i] | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
将此表数据作为实现该算法的测试数据。
【算法思想及处理过程】
1.定义了活动结构体Activity，包含活动的名称name、开始时间start和结束时间end。
2．定义了比较函数compare，用于按照活动的结束时间升序排序。
3．定义了一个活动安排函数activityArrangement，接受一个活动数组和活动个数作为参数，并按照活动结束时间排序后进行活动安排。
4．在活动安排函数中，首先使用sort函数对活动数组进行排序，排序规则是使用之前定义的比较函数compare。
5．输出第一个活动的信息。
6．初始化一个变量lastEnd，用于记录最后一个加入最大相容子集的活动的结束时间。
7．遍历剩下的活动数组，如果当前活动的开始时间晚于等于lastEnd，即活动不与已加入的活动冲突，将该活动加入最大相容子集，并更新lastEnd为该活动的结束时间。
8．输出结果。
在主函数中，首先获取用户输入的活动个数，然后根据输入的活动个数循环获取活动的名称、开始时间和结束时间。最后调用活动安排函数(activityArrangement)进行活动安排。
【程序代码】
#include
#include
using namespace std;
struct Activity {
int name;
int start;
int end;
};
bool compare(Activity a, Activity b) {
return a.end < b.end;
}
void activityArrangement(Activity activities[], int n) {
sort(activities, activities + n, compare);
cout << "结果为： "< cout << "Activite " << activities[0].name << "=" << activities[0].start << ", " << activities[0].end < int lastEnd = activities[0].end; for (int i = 1; i < n; i++) { if (activities[i].start >= lastEnd) { cout << "Activite "< lastEnd = activities[i].end; } } cout << endl; } int main() { int n; cout << "请输入活动个数: "; cin >> n; Activity activities[50]; for (int i = 0; i < n; i++) { cout << "请输入第"< cin >> activities[i].name >> activities[i].start >> activities[i].end; } activityArrangement(activities, n); return 0; }
【运行结果】
自行运行截图
【算法分析】
排序算法的时间复杂度：使用了STL的sort函数对活动数组进行排序，该函数的时间复杂度为 O(nlogn)，其中n为活动个数。
遍历活动数组的时间复杂度：在活动安排函数中，遍历了剩下的活动数组，时间复杂度为 O(n)，其中n为活动个数。
综上，代码的时间复杂度为 O(nlogn + n)，即 O(nlogn)。