C++ 活动选择程序

活动选择是组合优化中的一个问题。该问题可以表述如下：给定一组活动的开始时间和结束时间，选择单个个体可以执行的最大数量的活动，假设一个人一次只能进行一项活动。活动选择问题可以使用贪心算法解决，该算法在每一步都做出最佳选择，并且从不回头。活动选择问题贪心算法背后的关键思想是始终选择最早完成的活动，因为这将允许执行最大数量的活动。

为了实现活动选择问题的贪心算法，我们首先按活动结束时间的非降序对活动进行排序。排序后，我们从第一个活动开始，并将其包含在最大规模的活动子集中。然后，我们选择在当前活动结束时间之后开始的下一个活动，并将其包含在子集中。重复此过程，直到不能再向子集中添加活动。该算法可以以简单直接的方式实现，如下所示：

按活动结束时间的非降序对活动进行排序。

1. 将当前活动初始化为排序数组中的第一个活动。
2. 对于每个后续活动，如果其开始时间大于或等于当前活动的结束时间，则将其包含在子集中，并将当前活动更新为该活动。
3. 重复步骤 3，直到所有活动都被考虑。
4. 活动选择问题的贪心算法的时间复杂度为 O(n log n)，其中 n 是活动的数量。这是因为对活动进行排序需要 O(n log n) 时间，而算法的其余部分需要 O(n) 时间。

活动选择问题的贪心算法具有几个重要属性：

1. 最优子结构：如果活动选择问题的最优解包含某个特定活动，那么它也必须包含排序数组中该活动之前的所有活动。
2. 贪心选择性质：活动选择问题的贪心算法在每一步都做出局部最优选择，即选择最早完成的活动。此选择导致全局最优解。
3. 活动选择问题的贪心算法的正确性证明可以利用这两个属性来建立。实质上，可以证明在每一步选择最早完成活动的贪心选择导致问题的最优解。

C++ 代码

输出

The following activities are selected: 
(1, 2) (3, 4) (5, 7) (8, 9)

说明

总之，活动选择问题是可以使用贪心算法解决的经典问题示例。该问题的贪心算法实现简单，时间复杂度合理，并保证产生最优解。通过理解活动选择问题及其解决方案，我们可以更深入地欣赏贪心算法的强大和优雅，以及它们在解决优化问题方面提供的见解。