贪心算法告急！！！！！大神来帮忙！！！！！！有悬赏。。。。。一个问题叫做活动选择例4活动选择假设有一个需要使用某一资源的n个活动所组成的集合S，S={1,…,n}。该资

Question

贪心算法告急！！！！！大神来帮忙！！！！！！有悬赏。。。。。
一个问题 叫做活动选择
【例4】活动选择
假设有一个需要使用某一资源的n个活动所组成的集合S，S={1,…,n}。该资源一次只能被一个活动所占用，每一个活动有一个开始时间bi和结束时间ei(bi<=ei)。若bi>=ej或bj>=ei，则称活动i和活动j兼容。你的任务是：选择由互相兼容的活动所组成的最大集合。
输入：
输入文件名为act.in，共n+1行，其中第1行为n，第2行到第n+1行表示n个活动的开始时间和结束时间(中间用空格隔开)，格式为：
n
b1 e1
……
bn en

输出：
输出文件名为act.out，共两行，第1行为满足要求的活动占用的时间t，第2行为最大集合中的活动序号，每个数据之间用一个空格隔开。

样例输入：
11
3 5 样例输出：
1 4 14
12 14 2 3 6 8
8 12
0 6
8 11
6 10
5 7
3 8
5 9
2 13

这个题给出的贪心策略是：我们使用的贪心策略如下：每一步总是选择这样一个活动来占用资源：它能够使得余下的未调度的时间最大化，使得兼容的活动尽可能多(Why?)求助
为了达到这一目的，我们将n个待选活动按结束时间递增的顺序排列：e1’<=e2’<=…<=en’
首先让这一序列中的活动1进入集合S，再依次分析递增序列中的活动2，活动3，…，每次将与S中的活动兼容的活动加入到集合中。

这个题用贪心算法做为什么正确？？
题目上给的证明是：构造一个最优解，然后，对该解进行修正，使其第一步为一个贪心选择，证明总是存在一个以贪心选择开始的求解方案。
对于本题，设最优解为A，第一个选中的活动为k（k<>1），如果另一个解B开始于贪心选择活动1：
B = A – {k}∪{1}
因e1’<=ek’，所以B中的活动是兼容的。又因为B与A的活动数相同，所以B也是最优的。由此证明总存在一个以贪心选择开始的最优调度。
这个证明没看懂 请大神帮忙解释........

Answer 1

首先，这个题目的最优解（可能）并不是唯一的，将全体最优解记为集合Y（Y={y1,y2,...yn}）。
其次，题目中给出的贪心策略所得到的解（记为y）只是其中一个最优解，即y∈Y。
最后，就是怎么来证明贪心策略所得到的解是一个最优解，也就是怎么来证明y∈Y。
方法就是对于任意一个最优解yi（i∈[1,n]），可以通过一步修正得到另外一个最优解yj，然后对yj进行一步修正得到另外一个最优解，直到最优解变得跟y一模一样，也就证明了y是最优解。