用python语言实现“带时限的活动排序”问题的贪心算法，代码带点注释

用python语言实现“带时限的活动排序”问题的贪心算法，代码带点注释

可以参考下文实现

Python实现--贪心算法与活动安排问题_长歌丶的博客-CSDN博客_python活动安排问题 参考：http://blog.csdn.net/liufeng_king/article/details/8709005 如题：给出一组活动，告诉每个活动的开始时间和结束时间，要求出算出能参加的最多活动的数量或者活动的起止时间贪心算法思路：用两个数组s，f分别存储活动的起止时间，根据活动的结束时间对活动进行一个非减的活动序列，同样活动的开始时间list也要做对应的调整，这里博主是通过冒泡排序同步交 https://blog.csdn.net/qq_14908027/article/details/78827040

给你了

#proname:greedy_act
    #author:zhj
    #time:2019.10.29
    #language:python
    #version:1.0
#arg:tuple=>(0,1)
#return:tuple[1]=>1
def takeSecond(elem):
    return elem[1]
#arg:lst_id:[1,2,3,..,n]
#    lst_act:[(s[1],f[1]),(s[2],f[2]),...,(s[n],f[n])]
#return:sort of dict_act
# {1:(,*),2:(,**),...,n:(,**n)}
def sortAct(lst_id,lst_act):
    lst_sort_act = lst_act
    lst_sort_act.sort(key=takeSecond)
    dict_act = dict(zip(lst_id,lst_sort_act))
    return dict_act#test:success
#arg:dict_act
#{1:(,*),2:(,**),...,n:(,**n)}
#return:gree of gree_act[id:(,*),id:(,**),...,id:(,*****)]
def greedy(dict_act):
    true_id = []
    true_act = []
    #purpose: get the first to append the list
    true_ele_tuple = dict_act[1]
    true_id.append(1)
    true_act.append(true_ele_tuple)
    #purpose: get the  finish time of fist activity to divide element
    ele_divi = true_ele_tuple[1]
    for i in range(1,num_act):
#get the first act finish time
        id = int(1+i)
        #purpose:get the seconde activity to the last activity
        tuple_ele_act = dict_act[id]
        #print(tuple_ele_act) #test:success
        if (tuple_ele_act[0] >= ele_divi):
            true_id.append(id)
            true_act.append(tuple_ele_act)
            ele_divi = tuple_ele_act[1]
    greedy_act = dict(zip(true_id,true_act))
    return greedy_act
#main
input_act = input("请输入活动的个数，n = ")
num_act = int(input_act)
print("请分别输入开始时间s[i]和结束时间f[j]:")
lst_id = []
lst_act = []
for i in range(1,num_act+1):
    lst_id.append(i)
    input_start =eval(input("s["+str(i)+"]="))
    input_finish =eval(input("f["+str(i)+"]="))
    tuple = ()#purpose:def tuple to save the act_start and  act_finish
    tuple = (input_start,input_finish)
    lst_act.append(tuple)
    del tuple
    print("")
dict_act = sortAct(lst_id,lst_act)
print("按结束时间非减序排列如下：")
print("序号----开始时间----结束时间")
for i in range(1,num_act+1):
    id = int(i)
    ele_tuple = dict_act[i]
    print(id,"------",ele_tuple[0],"----------",ele_tuple[1])
#test；success
greedy_act = greedy(dict_act)
#print(greedy_act)#test:success
true_id = list(greedy_act.keys())
# print(true_id)#test:success
print("----------------------")
print("安排的活动序号依次为：")
printlen = len(true_id)
for id in true_id:
      tuple_print = greedy_act[id]
      print(id,"    ",tuple_print[0],"------>",tuple_print[1])