python贪心算法活动安排活动时间短优先

贪心算法是一种通过每一步的局部最优解来达到全局最优解的算法。对于活动安排问题，我们可以按照活动时间短的优先原则来进行贪心选择。

具体地，我们可以按照每个活动的结束时间从早到晚排序，然后从第一个活动开始，选择结束时间最早的活动，并将其加入已选活动集合中。接下来，我们继续从剩余的活动中选择结束时间最早的活动，并将其加入已选活动集合中，直到所有活动都被选完为止。

以下是 Python 代码实现：

def activity_selection(start, end):
    n = len(end)
    selected = [False] * n  # 记录每个活动是否被选中
    selected[0] = True
    last_end = end[0]  # 记录已选活动集合中最后一个活动的结束时间
    for i in range(1, n):
        if start[i] >= last_end:  # 检查当前活动和已选活动集合中最后一个活动是否有冲突
            selected[i] = True
            last_end = end[i]
    return [i for i in range(n) if selected[i]]  # 返回已选活动的下标集合

在这个代码中，`start` 和 `end` 分别是每个活动的开始时间和结束时间。函数 `activity_selection` 返回一个列表，表示被选中的活动的下标集合。

举个例子，如果有三个活动的开始时间和结束时间分别是：

start = [1, 3, 2]
end = [3, 5, 4]

按照上述贪心策略，我们应该优先选择第一个活动（结束时间为 3），然后选择第三个活动（结束时间为 4）。因此，`activity_selection(start, end)` 应该返回 `[0, 2]`。