实验：贪心算法
实验二：贪心算法
【实验目的】
应用贪心算法求解活动安排问题。
【实验性质】
验证性实验。
【实验要求】
活动安排问题是可以用贪心算法有效求解的很好的例子。
问题：有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 <iostream>
#include <algorithm>
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 << "结果为： "<<endl;
cout << "Activite " << activities[0].name << "=" << activities[0].start << ", " << activities[0].end <<endl;
int lastEnd = activities[0].end;
for (int i = 1; i < n; i++) {
if (activities[i].start >= lastEnd) {
cout << "Activite "<<activities[i].name <<"=" << activities[i].start << ", " << activities[i].end <<endl;
lastEnd = activities[i].end;
}
}
cout << endl;
}
int main() {
int n;
cout << "请输入活动个数: ";
cin >> n;
Activity activities[50];
for (int i = 0; i < n; i++) {
cout << "请输入第"<<i+1<<"次活动信息（名称 开始时间 结束时间） : ";
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)。