[TOC]
# 问题描述
设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si <fi。如果选择了活动i，则它在半开时间区间[si, fi)内占用资源。若区间[si, fi)与区间[sj, fj)不相交,则称活动i与活动j是相容的。也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。
# 算法思想
将活动按照结束时间进行从小到大排序。然后用i代表第i个活动，s[i]代表第i个活动开始时间，f[i]代表第i个活动的结束时间。按照从小到大排序，挑选出结束时间尽量早的活动，并且满足后一个活动的起始时间晚于前一个活动的结束时间，全部找出这些活动就是最大的相容活动子集合。事实上系统一次检查活动i是否与当前已选择的所有活动相容。若相容活动i加入已选择活动的集合中，否则，不选择活动i，而继续下一活动与集合A中活动的相容性。若活动i与之相容，则i成为最近加入集合A的活动，并取代活动j的位置。
例：设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：
算法greedySelector 的计算过程如下图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动。
# 分析
> 贪心策略认为：最早结束的活动一定在最优解中。这是解决问题的核心。
**证明最优解：**
设E = {1,2,3,...,n}为所给的活动集合。由于E中活动按结束时间的非递减序列排列，故活动1具有最早完成时间。
首先证明，活动安排问题有一个最优解以贪心选择开始，即该最优解中包含活动1.设A∈E是所给的活动安排问题的一个最优解，且A活动也按结束时间非减序排列，A中的第一个活动是活动k。
若k=1，则A就是一个以贪心选择开始的最优解。
若k>1，则设B=(A-{k})U{1}。由于f1<=fk，且A中活动是相容的，故B中活动也是相容的。
又B中的活动个数与A中的活动个数相等，且A是最优的，所以，B也是最优的。
也就是说，B是一个贪心选择的最优解。
所以，总存在贪心选择的最优解。（**贪心选择的证明**）
***
进一步，在做了贪心选择，即选择了活动1之后，原问题就简化为对E中所有与活动1相容的活动进行活动安排的子问题。
即若A是原问题的最优解，则A'=A-{1}是活动安排问题E'的最优解。
事实上，若能找到E'的一个最优解B'，它包含比A'更多的活动，则将活动1加入B'产生E的一个解B,它包含比A更多的活动。这与A的最优性矛盾。因此，每一步所做的贪心选择都是将问题化解为一个更小的与原问题相同的子问题。（**最优子结构的证明**）
# 实现代码-1
```
#include <stdio.h>
int
greedSelect(int s[],int f[],int A[],int n) {
int count=1;
int i,j=0;
A[0] = 1;
for(i=1;i<n;i++) {
if(s[i]>=f[j]) {
A[i] = 1;
j = i;
count++;
}
}
return count;
}
int
main(void) {
int s[] = {1,3,0,5,3,5,6,8,8,2,12};
int f[] = {4,5,6,7,8,9,10,11,12,13,14};
int A[11] = {0};
int s1 = greedSelect(s,f,A,11);
printf("s is %d",s1);
return 0;
}
```
