在蓝桥杯备考过程中，贪心算法中的活动选择问题是重要的考点之一。
一、活动选择问题的基本情况
活动选择问题简单来说，就是给定一系列的活动，每个活动都有开始时间和结束时间，要在这些活动中选择尽可能多的互不冲突的活动。
二、不同贪心策略
1. 最早结束时间策略
- 知识点内容：按照活动的结束时间进行排序，优先选择结束时间最早的活动。例如，有活动A(1, 4)、B(3, 5)、C(0, 6)、D(5, 7)、E(3, 8)、F(5, 9)、G(6, 10)、H(8, 11)。先选择A，因为它的结束时间4是最早的。然后下一个可以选的是D，因为D的开始时间5大于A的结束时间4。
- 学习方法：理解这种策略的关键在于认识到选择最早结束的活动可以为后续活动留下更多的时间。可以通过多做一些简单的实例来加深印象，比如自己随机设定一些活动的时间区间，然后按照这个策略去选择，看看能得到多少个不冲突的活动。
2. 最少资源占用策略（如果有资源相关的限制条件）
- 知识点内容：如果除了时间冲突外，还有资源占用的限制，比如场地、设备等。假设每个活动对某种资源的占用量不同，那么贪心的策略就是优先选择资源占用最少的活动，在满足资源限制的前提下再考虑时间冲突。例如，活动A需要1个单位的设备且(1, 4)时间进行，活动B需要0.5个单位设备且(3, 5)时间进行，在设备总量有限的情况下，先选B可能更优。
- 学习方法：构建包含资源因素的模型实例，对比不同选择顺序下资源的使用情况和最终能选择的活动数量。可以通过画图或者列表的方式来直观展示资源的变化情况。
三、贪心正确性证明思路
1. 贪心选择性质
- 要证明对于活动选择问题，按照我们所选的贪心策略（如最早结束时间策略）得到的解是局部最优解，并且最终可以得到全局最优解。以最早结束时间策略为例，假设存在一个最优解没有选择最早结束的活动。那么将这个最早结束的活动替换进去，由于它的结束时间最早，只要合理调整顺序，不会产生新的冲突，并且活动数量不会减少，所以原最优解不是真正的最优解。
2. 归纳法
- 可以从最少的活动数量开始归纳。当只有1个活动时，显然选择这个活动就是最优解。假设对于n - 1个活动按照贪心策略得到的解是最优的，那么对于n个活动，在前n - 1个活动已经按照贪心策略选择了最优解的基础上，再加入第n个活动，根据贪心策略进行选择，由于前面的假设和贪心选择性质，整体解仍然是最优的。
在备考过程中，要熟练掌握活动选择问题的不同贪心策略，并且能够清晰地阐述其正确性证明思路。多做练习题，包括不同难度层次的题目，从简单的几个活动到复杂的多活动、多限制条件的情况，并且尝试自己总结规律和解题技巧。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
