问题描述
已知一堆活动，他们有【开始时间】和【结束时间】，而同一时间你只能参加一个活动，如何选择参加活动的策略，尽可能地参加更多的活动？
有几种贪心策略：
- 贪开始最早
- 贪持续最短
- 贪结束最早
先来看开始最早，很容易找到反例，如图贪开始最早，那么选择红色的活动，显然不是最优解，因为选择蓝色的活动，可以参加2次，而红色活动只能参加一次
贪持续时间最短，显然也不对，特殊情况发生在最短时间的活动，位置刚好和其他活动冲突，如果选择时间最短的活动，也不是最优解
贪结束最早：证明
子定理证明：
先引入一个定理：最优解一定包含结束时间最早的活动，证明如下
假设活动a结束最早，可是我们能够找到一种方法A，使得不选a也能参加活动次数最多，假设A方法中结束时间最早的活动是b，那么只可能有如下情况;
ps：a与b不重叠的情况不存在，因为A答案已经是最优解了，如果ab不重叠，那么A答案仍然可以加入a活动，A答案不是最优解
- 因为a活动比b结束早（或者等于），而答案A中，b和下一个活动必定不冲突
- 而a早于b结束，可以轻易想到，a与答案A中的活动也不冲突
- 那么可以把b替换成a，对结果没有影响的，所以最优解一定有a，即最优解一定含结束最早的活动
那么假设最早结束的活动为a，某活动为b，那么我们先求得【b~最后一个活动】中的最优解B（子问题最优解），因为B一定包含b，所以只需要考虑向B中添加活动，看看最大能添加多少活动
子问题：【b~最后一个活动】中参加的最优解B
源问题：【a~最后一个活动】中参加的最优解
即子问题的答案为B，而我们尝试向子问题里添加活动，求解原问题，那么自然想到添加最不容易冲突的活动，即结束时间最早的活动