贪心法--活动安排问题

概述问题描述：现有一批活动，有开始时间和结束时间，如何合理的安排使得尽可能多的活动得以开展； 活动 讲座 会议 演出 电影 辩论赛 考试 开始时间 1 3 0 5 3 7 结束时间 3 4 4 7 6 8

问题描述：现有一批活动，有开始时间和结束时间，如何合理的安排使得尽可能多的活动得以开展；@H_502_1@

活动	讲座	会议	演出	电影	辩论赛	考试
开始时间	1	3	0	5	7
结束时间	4	7	6	8

解题思路：如何才能保证安排更多的活动呢？肯定是越早结束越好。所以首先对结束时间按升序排序，再依此选取符合的。比如说，肯定是先选讲座，然后可以选会议和演出，但是演出的开始时间是0，不符合，所以选会议，辩论赛开始时间是3，不符合所以选电影，最后选考试。@H_502_1@

首先是活动的定义：@H_502_1@

name=["讲座",会议演出电影辩论赛考试"]start=[1,3,5,7]end=[3,4,7,6,8]

然后，我们要对活动结束时间进行排序，同时，这种排序要影响到name和开始时间start。我们可以用元祖来进行配对，然后对元祖排序，相应的name和start也就改变了。@H_502_1@

name_end =List(zip(name,end))activity=sorted(activity,key=lambda x:x[1])name_end =sorted(name_end,1)">])print(activity)print(name_end)

@H_502_1@@H_502_1@

然后再重新取出start，end@H_502_1@

start = [i[0] for i in activity]end=[i[1]  activity](start)print(end)

@H_502_1@@H_502_1@

最后就是核心算法。由于结束时间已经是排好序的了，我们只要关注于开始时间，如果和前面的结束时间没有冲突，就可以进行这个活动。@H_502_1@

def greedy_activity(start,end,n):    #定义一个数组，用于存储该活动是否可以进行    tmp=[True for _  range(n)]    第一个活动肯定是可以进行的    j=0    遍历剩下的    in range(1,n):        如果开始时间大于前一个的结束时间        if start[i]>=end[j]:            则将其置为True            tmp[i]=True            当前的活动变为i            j=i        else:            否则该活动不能进行            tmp[i]=False    return tmp

最后，我们根据tmp数组查找哪些活动可以进行：@H_502_1@

tmp =in range(len(name_end)) if tmp[i]==True]print(res)

@H_502_1@@H_502_1@

也就是这四个活动。@H_502_1@

总结：贪心算法就是要让每一步都最优。 @H_502_1@ 总结

以上是内存溢出为你收集整理的贪心法--活动安排问题全部内容，希望文章能够帮你解决贪心法--活动安排问题所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。