[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;
}
```
