本节学习活动安排问题,各个活动使用同一资源,在活动之间如何取舍才能使举办的活动数量最多.这是一个非常经典的使用贪心算法的问题.

问题描述:

给定某一天活动的时间安排表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)