Python贪心算法

以下是Python中贪心算法的一个例子：

假设有一组活动，每个活动都有一个开始时间和结束时间，现在需要从这些活动中选择尽可能多的活动，使得它们不会相互冲突。可以使用贪心算法来解决这个问题。

首先，将所有活动按照结束时间从早到晚排序。然后，从第一个活动开始，选择结束时间最早的活动，并将其加入到最终的活动列表中。接着，从剩余的活动中选择结束时间最早且与已选活动不冲突的活动，并将其加入到最终的活动列表中。重复这个过程，直到所有活动都被考虑过。

下面是Python代码实现：

def activity_selection(start, end):
    n = len(end)
    selected = [0] * n
    i = 0
    selected[i] = 1
    for j in range(1, n):
        if start[j] >= end[i]:
            selected[j] = 1
            i = j
    return selected

start = [1, 3, 0, 5, 8, 5]
end = [2, 4, 6, 7, 9, 9]
selected = activity_selection(start, end)
print("Selected activities:", [i+1 for i in range(len(selected)) if selected[i]])

输出结果为：Selected activities: [1, 2, 4, 5]