题目
分析
这是一道典型的“贪心”问题。
其核心理解是：
- 在当前项目结束的时间（
end）确定时，选择可以启动——也就是项目启动时间（contest.start）在end之后——的项目中，结束时间（contest.end）最早的那个。 - 更新当前项目结束的时间（
end）为启动的那个项目的结束时间（contest.end）。
结构和排序
这里就涉及到排序问题了，而排序的是一个“模拟赛”。按照题意，一场比赛有开始和结束的时间。我们要对结束时间排序。所以用结构存储比赛信息最合理。
struct Contest
{
int start;
int end;
};相应的比较函数也很直截了当：
bool cmp(Contest &a, Contest &b)
{
return a.end < b.end;
}其余代码很直观，就不列出。请直接参考答案。
答案
思考
我们如何“证明”这个贪心的策略是合理的呢？
- 最优子结构性质：
如果我们已经选择了第一个结束最早的比赛，那么剩下的问题变成在剩余不与第一个比赛冲突的比赛中选择尽可能多的比赛，这是原问题的一个子问题。
- 贪心选择性质：
假设存在一个最优解S，其中第一个比赛不是结束最早的比赛。设A是结束最早的比赛，B是S中的第一个比赛。 我们可以构造一个新的解S'，用A替换B。由于A的结束时间早于B，所以A结束后能参加的比赛不会少于B结束后能参加的比赛。因此，S'至少包含与S相同数量的比赛，仍然是最优解。
通过这种方式，我们可以不断调整最优解，最终得到一个以结束时间最早的比赛开始的最优解，这证明了贪心选择是正确的。
- 归纳证明：
- 基础情况：当只有一个比赛时，选择它显然是最优的。
- 归纳步骤：假设对于
k个比赛，按结束时间排序的贪心策略能得到最优解。 - 对于
k+1个比赛，我们首先选择结束时间最早的比赛A，然后在剩余不与A冲突的比赛中应用相同的策略。根据归纳假设，这将给出剩余比赛的最优解。 - 结合前面的贪心选择性质，这证明了对于
k+1个比赛，该策略也能得到最优解。
这个贪心算法之所以正确，是因为它满足了贪心算法的两个关键性质：
- 最优子结构：问题的最优解包含子问题的最优解。
- 贪心选择性质：局部最优选择（选择结束最早的比赛）能导致全局最优解。
这是一个经典的贪心算法应用案例，也是贪心算法在区间调度问题中的标准解法。