备战蓝桥杯Day29 - 贪心-活动选择问题

本文主要是介绍备战蓝桥杯Day29 - 贪心-活动选择问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题描述

假设有n个活动，这些活动要占用同一片场地，而场地在某时刻只能供一个活动使用。
每个活动都有一个开始时间 si 和结束时间 fi (题目中时间以整数表示) ,表示活动在[si, f)区间占用场地。
问:安排哪些活动能够使该场地举办的活动的个数最多?

解决思路

贪心结论: 最先结束的活动一定是最优解的一部分
证明: 假设a是所有活动中最先结束的活动，b是最优解中最先结束的活动
如果a=b，结论成立
如果a不等于b，则b的结束时间一定晚于a的结束时间，则此时用a替换掉最优解中的b，a一定不与最优解中的其他活动时间重叠，因此替换后的解也是最优解。

首先，将所有活动按照结束时间 fi 进行排序。如果两个活动的结束时间相同，则按照开始时间 si 排序，以保证选择的确定性。
初始化一个空的活动列表，用于存储被选中的活动。
遍历排序后的活动列表，对于每个活动：
- 如果当前活动不与已选中的任何活动重叠（即当前活动的开始时间 si 大于等于已选中活动的最晚结束时间），则选择该活动，并将其添加到已选中的活动列表中。
- 否则，跳过该活动，继续检查下一个活动。
遍历结束后，已选中的活动列表就是能够使场地举办的活动个数最多的活动集合。

代码实现

activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
# 保证活动时间按照结束时间排好序
activities.sort(key=lambda x: x[1])def activity_selection(a):res = [a[0]]    # 排好序中的第一个一定是结束时间最早的for i in range(1, len(a)):# 活动不冲突的条件if a[i][0] >= res[-1][1]:res.append(a[i])return resprint(activity_selection(activities))

明天开始学习动态规划！