我得到了一个具有不同键和值的字典列表,其中一个是活动的持续时间,每个活动都有前导,我需要计算项目的总持续时间,为此,我需要找出何时活动开始和结束,然后获取结束值中的最大值。我不知道如何编写代码来获取开始值和结束值。
activities = [
{'Cost': 10000, 'Duration': 5, 'Name': 'Activity 1', 'Predecessors': None},
{'Cost': 8000, 'Duration': 3, 'Name': 'Activity 2', 'Predecessors': ['Activity 1']},
{'Cost': 2000, 'Duration': 15, 'Name': 'Activity 3', 'Predecessors': ['Activity 2', 'Activity 1']},
{'Cost': 7000, 'Duration': 16, 'Name': 'Activity 4', 'Predecessors': ['Activity 2']},
{'Cost': 5000, 'Duration': 20, 'Name': 'Activity 5', 'Predecessors': ['Activity 4']},
这是我得到的一部分。
def get_total_project_duration(activities: list) -> int:
start = 0
finish = {}
for activity in activities:
predecessors = activity['Predecessors']
if not predecessors:
finish[activity['Name']] = 0 + activity['Duration']
else:
for pred in predecessors:
for value in activities:
if value['Name'] == pred:
start += value['Duration']
finish[activity['Name']] = start+activity['Duration']
start = 0
totalDuration = max(finish.values())
return totalDuration
这是我尝试过的,但没有成功。
这是一种必须先向你展示“技巧”的问题。
这里的关键是,只有当一个活动的所有前一个活动都已经完成时,你才能知道它的终点。因此,您需要继续浏览列表,对于每个未完成的条目,找出其所有前任条目是否已完成。如果有,您可以记住它的终点,然后继续下一个。
请注意,可以构建一个带有循环或未连接的“岛”的图,这会导致此代码无限循环。我想他们不会给你吃其中之一。
activities = [
{'Cost': 10000, 'Duration': 5, 'Name': 'Activity 1', 'Predecessors': None},
{'Cost': 8000, 'Duration': 3, 'Name': 'Activity 2', 'Predecessors': ['Activity 1']},
{'Cost': 2000, 'Duration': 15, 'Name': 'Activity 3', 'Predecessors': ['Activity 2', 'Activity 1']},
{'Cost': 7000, 'Duration': 16, 'Name': 'Activity 4', 'Predecessors': ['Activity 2']},
{'Cost': 5000, 'Duration': 20, 'Name': 'Activity 5', 'Predecessors': ['Activity 4']}
]
def get_total_project_duration(activities: list) -> int:
start = 0
finish = {}
unfinished = len(activities)
while unfinished:
for activity in activities:
if activity['Name'] not in finish:
latest = 0
for pred in activity['Predecessors'] or []:
if pred not in finish:
latest = -1
break
latest = max(latest, finish[pred])
if latest >= 0:
print(latest, activity)
finish[activity['Name']] = latest + activity['Duration']
unfinished -= 1
return max(finish.values())
print(get_total_project_duration(activities))
输出:
0 {'Cost': 10000, 'Duration': 5, 'Name': 'Activity 1', 'Predecessors': None}
5 {'Cost': 8000, 'Duration': 3, 'Name': 'Activity 2', 'Predecessors': ['Activity 1']}
8 {'Cost': 2000, 'Duration': 15, 'Name': 'Activity 3', 'Predecessors': ['Activity 2', 'Activity 1']}
8 {'Cost': 7000, 'Duration': 16, 'Name': 'Activity 4', 'Predecessors': ['Activity 2']}
24 {'Cost': 5000, 'Duration': 20, 'Name': 'Activity 5', 'Predecessors': ['Activity 4']}
44