区间调度问题贪心算法证明

区间调度问题是指在一些活动中选择一些互不冲突的活动，使得能够完成的活动数最多。贪心算法是一种常用的解决该问题的方法。下面是该算法的证明过程：

假设存在最优解S，其中包含n个活动。我们将这些活动按照结束时间的先后顺序排列，即e1≤e2≤...≤en。我们用A1表示S中结束时间最早的活动，用Ak表示S中结束时间最晚的活动。我们假设Ak不在贪心算法得到的结果集中，而是选择了另一个活动Aj。因为Ak结束时间最晚，所以Aj的结束时间一定不晚于Ak，即ej≥ek。而根据贪心算法，Ak是在所有结束时间不早于ej的活动中结束时间最晚的，所以Ak的结束时间不晚于Aj，即ek≥ej。因此，ej=ek，即Ak和Aj的结束时间相同。但是，由于Ak是S中结束时间最晚的活动，所以Aj不可能在S中，与假设矛盾。因此，Ak一定在贪心算法得到的结果集中。

接下来，我们用数学归纳法证明贪心算法得到的结果集是最优解。假设贪心算法得到的结果集为S，其中包含m个活动。我们将这些活动按照结束时间的先后顺序排列，即e1≤e2≤...≤em。我们用B1表示S中结束时间最早的活动，用Bk表示S中结束时间最晚的活动。我们假设Bk在最优解中的位置是i，即Bk是最优解中的第i个活动。因为Bk是S中结束时间最晚的活动，所以在最优解中，前i-1个活动的结束时间一定不晚于ek，即ei-1≥ek。而根据贪心算法，Bk是在所有结束时间不早于ei-1的活动中结束时间最晚的，所以Bk的结束时间不早于最优解中前i-1个活动的结束时间，即ej≥ei-1。因此，ei-1≥ek≤ej，即Bk和Bi-1的结束时间相同。但是，由于Bk是最优解中结束时间最晚的活动，所以Bi-1不可能在最优解中的位置在i之后，即Bi-1在最优解中的位置一定在i之前。因此，我们可以将Bi-1替换成Bk，得到一个包含m-1个活动的最优解。根据数学归纳法，贪心算法得到的结果集是最优解。