如何计算项目总时长？基于活动依赖的Python代码求助

问题描述 #

我有一个由多个字典组成的活动列表，每个字典包含Cost、Duration、Name、Predecessors等字段，Duration为活动时长，每项活动存在前置依赖。需要计算各活动的开始与结束时间，取结束时间的最大值得到项目总时长，但不清楚如何正确实现。

示例活动数据 #

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

代码问题分析 #

你的代码存在两个核心错误：

1. 错误累加前置活动时长：当前逻辑把所有前置活动的时长相加作为当前活动的开始时间，这不符合项目依赖逻辑——正确逻辑应该是取所有前置活动的最晚结束时间作为当前活动的最早开始时间。
2. 未处理活动顺序问题：如果活动列表顺序不是拓扑序（即前置活动出现在当前活动之后），计算当前活动时前置活动的结束时间还未被记录，会导致结果错误。

正确实现方案 #

核心思路 #

1. 将活动列表转为字典，通过活动名快速查找活动信息。
2. 用拓扑排序确保处理每个活动时，其所有前置活动已计算完成。
3. 计算每个活动的最早开始时间（取所有前置活动结束时间的最大值，无前置则为0），再推导最早结束时间。
4. 所有活动结束时间的最大值即为项目总时长。

正确代码 #

from collections import deque

def get_total_project_duration(activities: list) -> int:
    # 转字典，通过活动名快速查询
    activity_map = {act['Name']: act for act in activities}
    # 记录每个活动的前置依赖数量（入度）
    in_degree = {}
    # 构建邻接表：记录每个活动的后续活动
    adjacency = {}
    
    for act_name, act in activity_map.items():
        preds = act['Predecessors']
        in_degree[act_name] = len(preds) if preds else 0
        adjacency[act_name] = []
        # 为每个前置活动添加后续关联
        if preds:
            for pred in preds:
                adjacency[pred].append(act_name)
    
    # 初始化最早开始/结束时间
    earliest_start = {}
    earliest_finish = {}
    # 拓扑排序队列：先加入无前置的活动
    queue = deque()
    
    for act_name in in_degree:
        if in_degree[act_name] == 0:
            earliest_start[act_name] = 0
            earliest_finish[act_name] = activity_map[act_name]['Duration']
            queue.append(act_name)
    
    # 处理每个活动
    while queue:
        current = queue.popleft()
        # 更新所有后续活动的最早开始时间
        for neighbor in adjacency[current]:
            in_degree[neighbor] -= 1
            # 取当前已有的最早开始时间和当前前置的结束时间的最大值
            if neighbor not in earliest_start:
                earliest_start[neighbor] = earliest_finish[current]
            else:
                earliest_start[neighbor] = max(earliest_start[neighbor], earliest_finish[current])
            # 所有前置处理完成后，计算结束时间并加入队列
            if in_degree[neighbor] == 0:
                earliest_finish[neighbor] = earliest_start[neighbor] + activity_map[neighbor]['Duration']
                queue.append(neighbor)
    
    # 返回最大结束时间
    return max(earliest_finish.values())

# 测试
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']},
]

print(get_total_project_duration(activities))  # 输出：39

代码说明 #

• 拓扑排序：保证活动处理顺序符合依赖关系，避免前置未处理就计算当前活动。
• 邻接表+入度：高效管理活动间的依赖关联，准确判断活动是否可处理。
• 时间计算：严格遵循项目管理中最早开始/结束时间的规则，确保结果准确。

内容的提问来源于stack exchange，提问作者Ericka Salinas