Pygorithm项目中的贪心算法：活动选择问题解析

什么是活动选择问题

活动选择问题是计算机科学中一个经典的贪心算法应用场景。该问题的核心是：给定一组活动，每个活动都有开始时间和结束时间，如何安排才能让一个人参与最多的活动数量？前提条件是同一时间只能参与一个活动。

这个问题在实际生活中有广泛应用，比如会议室安排、课程表制定、任务调度等场景。

Pygorithm中的实现解析

Pygorithm项目提供了一个清晰的活动选择问题实现，主要包含以下几个关键部分：

输入参数

def activity_selection(start_times, finish_times):

函数接收两个参数：

• start_times: 活动开始时间列表
• finish_times: 活动结束时间列表

输入验证

实现中包含了严格的输入验证：

1. 检查输入是否为列表类型
2. 检查两个列表长度是否一致

if type(start_times) is not list:
    raise TypeError("Activity selection problem only accepts lists...")

if len(start_times) != len(finish_times):
    raise ValueError('Length of start_times list and finish_times list must be same')

算法核心逻辑

算法采用贪心策略，步骤如下：

1. 首先选择第一个活动
2. 然后遍历剩余活动，选择第一个与前一个选中活动不冲突的活动（开始时间≥前一个活动的结束时间）
3. 重复上述过程直到遍历完所有活动

i = 0
activity.append(i)

for j in range(n):
    if start_times[j] >= finish_times[i]:
        activity.append(j)
        i = j

代码获取功能

def get_code():
    return inspect.getsource(activity_selection)

这个辅助函数可以返回算法实现的源代码，方便学习者查看。

算法复杂度分析

该实现的时间复杂度为O(n)，其中n是活动数量。因为只需要一次线性扫描即可完成选择。

空间复杂度也是O(n)，最坏情况下需要存储所有活动的索引。

贪心算法正确性证明

为什么这种贪心选择能得到最优解？关键在于：

1. 活动已按结束时间排序（实现中假设输入已排序）
2. 每次选择最早结束且不与已选活动冲突的活动
3. 这样可以为后续活动留下最多的时间

这种选择策略能保证全局最优，是贪心算法的典型应用。

实际应用建议

在实际使用时需要注意：

1. 输入的活动应该已经按照结束时间排序，如果未排序需要先排序
2. 开始时间和结束时间应该合理，结束时间不应早于开始时间
3. 时间单位要一致（都使用分钟或小时等）

扩展思考

可以尝试扩展这个算法解决以下变种问题：

1. 每个活动有不同的权重，求最大权重和而非最多活动数
2. 有多个资源（多人）时的活动安排问题
3. 活动有优先级时的选择问题

Pygorithm的这个实现为我们理解贪心算法和活动选择问题提供了很好的基础，值得深入学习和研究。