1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
| #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])
|