本节学习活动安排问题,各个活动使用同一资源,在活动之间如何取舍才能使举办的活动数量最多.这是一个非常经典的使用贪心算法的问题.
问题描述:
给定某一天活动的时间安排表time,time[i][0]和time[i][1]分别表示各个活动的开始时间和结束时间,由于各个活动使用的是同一片场地,试问如何安排活动能使场地举办的活动最多.
思路解析:
优先选取结束时间早的活动,可以为未举办的活动尽可能的预留时长,然后判断下一个活动的开始时间是否在当前活动的结束时间后.若是,则选取该活动,若否,则对下一个活动进行判断.变量如下:
Time变量:表示各个作业所需时间
Re变量:表示所有被选取活动的时间的集合
完整代码如下:
def activity(time):# 初始化一个空列表re，用来存储不重叠的活动re = []# 对输入的时间列表time按照结束时间进行排序time.sort(key=lambda x: x[1])# 将排序后的第一个活动（最早结束的活动）添加到结果列表re中re.append(time[0])# 从time列表的第二个元素开始遍历，因为第一个元素已经被添加到re中了for t in time[1:]:# 如果当前活动的开始时间不早于re列表中最后一个活动的结束时间，则这两个活动不重叠if t[0] >= re[-1][1]:# 将当前活动添加到re列表中re.append(t)# 返回不重叠的活动列表re以及这些活动的总数return re, len(re)