任务依赖总时长：无限并行关键路径与M处理器区别

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 任务不可拆、持续时间非负，边u→v要求u完成后v才能开始；无限处理器且无通信开销。
• M个CPU的追问不能直接沿用关键路径结果，它只是下界；是否抢占、资源差异另需明确。

解题路线

1. Kahn拓扑序计算start[v]=max finish[pred]，finish[v]=start[v]+duration[v]，总时长取最大finish。重复边先去重避免入度错。
2. 任意依赖链必须串行，关键路径长是下界；无限资源下每个任务一旦依赖完成就运行，归纳得到算法恰达到下界。
3. 有限M同时满足总工作量/M与关键路径两个下界，但不一定可同时达到。可给ready队列list scheduling近似并说明不是精确最优；若面试要精确最小makespan，需要规模受限状态搜索及上界剪枝。

手动走一遍

A3→C4，B5→C4：A/B同时开始，C在5开始9结束，总9。两个独立5单位任务，无限CPU总5，M1总10；不应仍返回5。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

from collections import deque

def makespan(durations,edges):
    if any(t<0 for t in durations):raise ValueError("negative duration")
    n=len(durations);nexts=[set() for _ in range(n)];degree=[0]*n
    for u,v in edges:
        if not (0<=u<n and 0<=v<n):raise ValueError("unknown task")
        if v not in nexts[u]:nexts[u].add(v);degree[v]+=1
    ready=deque(i for i in range(n) if degree[i]==0);start=[0]*n;finish=[0]*n;count=0
    while ready:
        u=ready.popleft();count+=1;finish[u]=start[u]+durations[u]
        for v in nexts[u]:
            start[v]=max(start[v],finish[u]);degree[v]-=1
            if degree[v]==0:ready.append(v)
    if count!=n:raise ValueError("dependency cycle")
    return max(finish,default=0),start,finish

复杂度

DAG O(V+E)时间/空间。有限机一般前置约束调度需另算法，不能把O(V+E)宣称为全部追问复杂度。

易错点与追问

容易失分的边界

• 求所有duration总和会忽略并行。
• 图有环时没有合法完成顺序，应返回错误而非部分任务max。

继续深挖

• 固定M的优先级可如何用到终点的剩余关键路径？
• 若任务可抢占和迁移，哪些下界仍有效？