如何获取项目总工期

Question

我得到了一个具有不同键和值的字典列表，其中一个是活动的持续时间，每个活动都有前导，我需要计算项目的总持续时间，为此，我需要找出何时活动开始和结束，然后获取结束值中的最大值。我不知道如何编写代码来获取开始值和结束值。

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

这是我尝试过的，但没有成功。

Answer 1

这是一种必须先向你展示“技巧”的问题。

这里的关键是，只有当一个活动的所有前一个活动都已经完成时，你才能知道它的终点。因此，您需要继续浏览列表，对于每个未完成的条目，找出其所有前任条目是否已完成。如果有，您可以记住它的终点，然后继续下一个。

请注意，可以构建一个带有循环或未连接的“岛”的图，这会导致此代码无限循环。我想他们不会给你吃其中之一。

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

Answer 2

我会首先重塑活动以使查找更容易......

## Reshape activities to make searching by name easier
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']},
]
activities = {activity["Name"]: activity for activity in activities}

现在我将通过递归查找必须为任何给定活动处理的不同活动列表来解决这个问题。

注意，我假设任何给定的活动一旦完成就足以满足该任务的每个必需先决条件，并且没有两个任务并行运行。

def distinct_names(name):
    names = set([name])
    for name in activities[name]["Predecessors"] or []:
        names = names.union(distinct_names(name))
    return names

现在要查找给定活动的持续时间，我们只需获取不同活动的列表并将其持续时间相加...

for activity in activities.values():
    total = sum(activities[name]["Duration"] for name in distinct_names(activity["Name"]))
    print(activity["Name"], total)

赠送一个：

Activity 1 5
Activity 2 8
Activity 3 23
Activity 4 24
Activity 5 44

该组活动的总持续时间将是最长的：

print(max(
    sum(activities[name]["Duration"] for name in distinct_names(activity["Name"]))
    for activity in activities.values()
))