活动选择问题
活动选择问题（Activity Selection Problem）是贪心算法的经典应用。
问题描述
每门课都有其上课时间和下课时间，不同课程不能出现时间冲突。目标是找到一种排课方式，使得排课数量最多同时不出现冲突。
贪心策略
选择结束时间最早的活动，证明该策略能得到最优解。
可以证明：存在一个优化解，结束时间最早的活动一定在优化解之中。
优化解具有子结构：去掉结束时间最早的活动后，剩余的活动组成是对剩下时间的最优解。
算法实现
简单来说：
- 对原活动按照结束时间进行排序
- 将第一个活动加入解集
- 从下一个活动开始遍历，如果其开始时间不小于解集最后元素的结束时间，就把该活动加入解集并更新结束时间
算法分析
时间复杂度主要由排序决定，为 O(n log n)。
链接到
- 上一个知识点：3.1 贪心算法原理
- 下一个知识点：无（本章最后一个知识点）