用Python实现贪心算法活动安排问题

在Python中，我们可以使用贪心算法解决活动安排（也称为任务调度）问题。这种问题通常涉及找到一种安排方式，使得完成所有活动的时间最短，或者满足某些优先级条件。这里以经典的“活动选择”问题为例，每个活动有一个开始时间和结束时间，我们要确定可以参加的活动序列，以便覆盖尽可能多的活动且不会冲突。

以下是一个简单的贪心算法实现：

def activity_selection(activities, n):
    activities.sort(key=lambda x: x[1])  # 按结束时间升序排列
    selected = []
    i = 0

    while i < n and len(selected) < n:
        start_time = activities[i][0]

        # 查找下一个可以开始的活动，不会与已选活动冲突
        for j in range(i+1, n):
            if activities[j][0] > start_time:
                selected.append(activities[j])
                break
        i += 1

    return selected

# 示例
activities = [(1, 2), (3, 4), (0, 5), (6, 7)]
n = len(activities)
selected_activities = activity_selection(activities, n)

for act in selected_activities:
    print(f"活动 {act[0]} 到 {act[1]} 可以参加")

在这个例子中，我们首先按结束时间对活动排序，然后从最早的活动开始，检查后续活动中是否有比当前活动更晚的开始时间。如果有，则选择那个新的活动并更新搜索范围。这样做的关键是保证了每次添加的新活动都不会与之前已选的活动发生时间冲突。