CJTX04｜活动安排 题解

核心算法

按结束时间从小到大排序，每次选择当前能参加且结束最早的活动。

思路推导

结束越早，给后续活动留下的时间越多。维护上一个已选活动的结束时刻 lastEnd。依次扫描按结束时刻排序的活动，若当前活动满足 $l_i\ge lastEnd$，就选择它并更新 lastEnd。

正确性说明

在所有可作为当前第一个活动的候选中，贪心选择结束最早的活动 $G$。任取一个最优方案，其第一个活动为 $O$。因为 $G$ 的结束时间不晚于 $O$，把 $O$ 替换为 $G$ 后，原方案后续所有活动仍然可参加，活动总数不减少。对剩余时间段重复该论证，贪心方案最优。

复杂度

• 时间复杂度：$O(n\log n)$；
• 空间复杂度：$O(n)$。

易错点

• 排序关键字是结束时间，不是开始时间，也不是持续时间；
• 允许首尾相接，判断条件应为 l >= lastEnd；
• 区间完全包含、结束时间相同等情况必须正确处理。