题目重点：用拓扑顺序计算最早完成时间，证明关键路径下界可实现，辨别环、重复边与有限worker追问。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 依赖 u→v 表示u完成后v才能开始，所有任务都要执行；duration为非负整数。
- 任务不可拆分，通信、切换和资源争用成本在训练合同中忽略。
- 重复边只表示同一个依赖；有环报错，空任务集合耗时零。
解题路线
- 任何依赖链上的任务都必须串行，因此其duration总和是完成时间下界。最长依赖链也就是关键路径；全部duration相加只有所有任务恰好在一条链上才成立。
- 令 earliest_finish[v]=duration[v]+max(earliest_finish[u])，其中u是所有直接前置。无前置时从0开始，finish等于自身duration。max体现等待最慢前置，并非把所有前置耗时相加。
- 用Kahn拓扑算法，入度零的任务可先计算。移除u时向后继v传播 finish[u]+duration[v]；v只有全部前置都移除后才入队。节点ID大小不代表执行次序。
- 无限资源下，把每项任务在其所有前置完成时立即开始，这个构造可实现递推给出的时间。它满足每条依赖，因此达到最长链下界，最优性来自下界与可实现排程一致。
- 若拓扑处理数小于任务数，存在依赖环，不能返回部分任务的finish当总答案；duration=0也不应自动消除环，因为题目仍给了无法满足的先后约束。
- 进一步可保留导致最大finish的前置，回溯给出一条关键路径。多个并列最长路径任选或全部列出；列出全部可能指数多。有限worker时，这个值仅是下界，还要考虑机器负载，不可原样作为最优makespan。
手动走一遍
A耗时3、B耗时5，均完成后C耗时2；A/B从0并行，C在5开始，总7，而不是10。若A→B→C则总10。两条独立链完成时间4和9，总时间9；把它们相加会错误地假设资源只能串行。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Task IDs 0..n-1, edges prerequisite -> dependent, nonnegative durations."""
from collections import deque
def minimum_finish_time(durations, dependencies):
n = len(durations)
if any(not isinstance(d, int) or isinstance(d, bool) or d < 0 for d in durations):
raise ValueError("nonnegative integer durations required")
children = [[] for _ in range(n)]
indegree = [0] * n
edges = set()
for u, v in dependencies:
if not (isinstance(u, int) and isinstance(v, int)) or isinstance(u, bool) or isinstance(v, bool) or not (0 <= u < n and 0 <= v < n):
raise ValueError("invalid task ID")
if (u, v) not in edges:
edges.add((u, v))
children[u].append(v)
indegree[v] += 1
finish = list(durations)
ready = deque(i for i in range(n) if indegree[i] == 0)
visited = 0
while ready:
u = ready.popleft()
visited += 1
for v in children[u]:
finish[v] = max(finish[v], finish[u] + durations[v])
indegree[v] -= 1
if indegree[v] == 0:
ready.append(v)
if visited != n:
raise ValueError("dependency cycle")
return max(finish, default=0)
复杂度
拓扑与动态规划 O(V+E)，邻接/去重集合/入度/finish O(V+E) 空间。大duration用宽整数；有限资源调度与本题复杂度不同。
易错点与追问
容易失分的边界
- 把多前置finish相加。
- 根据任务编号遍历而不是拓扑。
- 重复边入度和邻接计数不一致。
- 有环返回局部结果。
- 无限并行假设下错误加入worker队列。
继续深挖
- 怎样返回关键路径与每项开始时刻？
- 新增一条依赖如何增量更新？
- 若只有K个worker，下界有哪些？
- 失败重试是否改变固定duration合同？
