第一部分 基础算法

第 1 章 贪心算法

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最优的算法。尽管贪心算法不能保证在所有情况下都能得到全局最优解，但在许多具有特定结构的问题中，贪心策略往往能高效地给出正确且最优的解。其核心在于“贪心选择性质”，即局部最优选择能够导致全局最优解。

#10000 「一本通 1.1 例 1」活动安排

这道题是贪心算法的经典入门案例。问题描述为：给定 n 个活动，每个活动有开始时间和结束时间，求最多能参加多少个互不冲突的活动。解决此类区间调度问题，最常用的贪心策略是按结束时间排序。直觉上，尽早结束的活动能为后续活动留出更多空间。我们将所有活动按照结束时间从小到大排序，然后依次遍历，如果当前活动的开始时间大于或等于上一个已选活动的结束时间，则选择该活动。这种策略保证了在每一步都选择了“最早结束”的可行活动，从而最大化了剩余可用时间，最终得到最大数量的活动。

#10001 「一本通 1.1 例 2」种树

本题要求在一排位置上种树，使得任意两棵相邻的树之间距离满足特定条件，或者更常见的是，给定一些限制条件，求最少需要种多少棵树以满足所有条件，或者在满足条件下求最大/最小值。通常这类问题可以通过将条件转化为区间覆盖或点选择问题来解决。例如，如果要求某些位置必须被