Python 中活动选择问题的贪心解法
活动选择问题是指在一些活动中选择尽可能多的活动，使得这些活动不冲突，即它们的时间不重叠。这是一个经典的贪心问题，可以用贪心算法来求解。
贪心策略：按照活动结束时间升序排序，优先选择结束时间早的活动。
代码实现：
def activity_selection(start_time, end_time): n = len(start_time) activities = [] for i in range(n): activities.append((start_time[i], end_time[i])) activities.sort(key=lambda x: x[1]) # 按结束时间升序排序 selected = [activities[0]] # 初始化选择第一个活动 for i in range(1, n): if activities[i][0] >= selected[-1][1]: selected.append(activities[i]) # 选择不冲突的活动 return [activities.index(activity) for activity in selected] # 返回选择的活动在列表中的索引 # 示例 start_time = [1, 3, 0, 5, 8, 5] end_time = [2, 4, 6, 7, 9, 9] indices = activity_selection(start_time, end_time) for i in indices: print("活动{}：开始时间{}，结束时间{}".format(i, start_time[i], end_time[i]))
输出：
活动0：开始时间1，结束时间2 活动1：开始时间3，结束时间4 活动3：开始时间5，结束时间7 活动4：开始时间8，结束时间9
相关文章