贪心算法求解最大安排相容活动个数，时间管理符合最优解求法

问题描述：

假设有n个活动的集合E={a1,a2,…,an}，其每个活动都要求使用同一资源（如某个设备、教室、场地等），而在同一时间内只允许一个活动使用这一资源。

每个活动都有一个要求使用该资源的起止时间si,fi，且si<fi。如果选择了活动ai，则它在半开的时间区间[si,fi)内占有资源。两个活动ai,aj称为是相容的，当且仅当它们的时间区间[si,fi)和[sj,fj)不相交，即si>=fj 或 sj >=fi。现要求在所给定的活动集中选出最大的相容活动子集。（提示：贪心策略）

主函数已经给出， 请补充 Sort 和 Select 函数。 答案区只提交两个函数代码，不允许补充或修改其他代码！

#define Maxn 100
//定义活动的类型
typedef struct act_Node
{ int Id; //活动ID
int s_Time; //活动开始时间
int f_Time; //活动结束时间
} ACND;
// ******** Sort 函数 **********
// ******** Select 函数 **********
int main()
{ ACND arr[Maxn];
int an,i;
cin>>an; //读入活动个数
//读入各个活动的编号和占用资源的起止时间
for(i=0;i<an;i++)
cin>>arr[i].Id>>arr[i].s_Time>>arr[i].f_Time;
Sort(an,arr);
Select(an,arr);
return 0;
}
输入，有多行，第1行是活动的个数n，后面n行，每行3个整数，是每个活动的编号、占用资源的开始时间、结束时间
输出，选出的最大活动子集，即有多行，每行包括活动的编号、开始时间、结束时间。
例如:
输入：
11
1 3 8
2 2 13
3 1 4
4 5 7
5 6 10
6 8 11
7 12 14
8 5 9
9 3 5
10 0 6
11 8 12
输出：
3：1-4
4：5-7
6：8-11
7：12-14

贪心算法：
(1)原理：
在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
(2)特性：
贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。能够用贪心算法求解的问题一般具有两个重要特性：贪心选择性质和最优子结构性质。
代码实现：

#include<bits/stdc++.h>
//懒得写排序函数引入sort()函数，可忘了算法单词怎么拼写
bool cmp(ACND a, ACND b){//为结构体写引入排序函数
	if(a.f_Time == b.f_Time)
		return a.s_Time< b.s_Time;
		//这一步应该是多余的，保证按时间结束排序就行
	return a.f_Time < b.f_Time;
}
void Sort(int an,ACND *arr){
//sort（）排序
	 sort(arr,arr+an,cmp);
}
void Select(int an,ACND *arr){
	int flag[an], flag2 =0; //标记数字
	//测试网站不支持数组初始为{0}
	flag[0]=0;//标记数组
	for(int i=1;i<an;i++){
		if(arr[flag[flag2]].f_Time <= arr[i].s_Time )
		//当后活动时间大于加入相容活动最后的结束时间
			flag[++flag2] = i;
	}
	for(int i =0;i<=flag2;i++){
		//输出
		printf("%d:%d-%d\n",arr[flag[i]].Id,arr[flag[i]].s_Time,arr[flag[i]].f_Time);
	}
}