教程目录

想要实际看看算法是如何工作的吗?

通过交互式可视化深入理解算法运行过程

查看算法可视化

活动选择问题

介绍

活动选择问题是贪心算法的经典应用场景,核心思想是从一系列活动中选择最大数量的互不冲突的活动。这个问题在资源调度和时间管理领域有着广泛应用。

活动选择问题可以通过贪心策略高效求解,时间复杂度为O(n log n)(主要来自于排序),n是活动的数量。

问题定义

给定n个活动,每个活动都有一个开始时间si和结束时间fi(si < fi)。两个活动i和j是兼容的,si ≥ fj或sj ≥ fi(即一个活动的开始时间不早于另一个活动的结束时间)。活动选择问题要求选择最大数量的互相兼容的活动。

例如,给定以下活动列表(开始时间, 结束时间):
[(1,4), (3,5), (0,6), (5,7), (3,9), (5,9), (6,10), (8,11), (8,12), (2,14), (12,16)]

最优解为选择活动:(1,4), (5,7), (8,11), (12,16),共4个活动。

算法步骤

  1. 将所有活动按照结束时间升序排序

...

目录