1. 问题
设S={1,2,…,n}为活动的集合，si和fi分别为活动i的开始和截止时间，i = 1,2…n。求出一个活动序列，使得这个序列中任意两个活动i,j满足 si=<fj或者sj =< fi(即不相容).
2. 解析
主要使用贪心算法来对问题进行解决，主要策略是把活动按照截止时间从小到大排序，然后从前向后挑选，只要与前面选中的活动相容，就可以把活动选入。
贪心算法反例：把活动按照开始时间从小到大排序，然后从前向后挑选，只要与前面选中的活动相容，就可以把活动选入。
正常贪心：
|
i |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
Si |
3 |
1 |
3 |
3 |
7 |
3 |
1 |
3 |
6 |
8 |
|
Fi |
4 |
5 |
5 |
6 |
8 |
8 |
9 |
9 |
10 |
10 |
反例贪心：
|
i |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
Si |
1 |
1 |
3 |
3 |
3 |
3 |
3 |
6 |
7 |
8 |
|
Fi |
5 |
9 |
4 |
5 |
6 |
8 |
9 |
10 |
8 |
10 |
由表可以看出反例求出的最大值并不正确
3. 设计
对所有活动进行排序
Sep来存储上次选中的活动的结束时间，初始化为0
For I from 0 to 活动的数量
如果活动i的开始时间 >= sep
将活动i选出
将活动i的结束时间设置为sep
4. 分析
算法主要有两部分组成，选活动与排序，选活动就进行了一次遍历，复杂度为n，排序的复杂度为O(nlogn),因此整体复杂度为O(nlogn)