Uber 并行任务 DAG：单位时长的最短完工时间

题意与假设

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

• 任务编号为 0..n−1；边 (u,v) 表示 u 完成后 v 才能启动。不同任务可无限并行，且每任务恰好耗时 1 单位。
• 所有任务都必须完成；n=0 返回 0。重复依赖边按同一关系去重，避免入度与释放次数不一致。
• 若依赖图有环，任务无法全部完成，代码报错；题目未规定错误返回格式。

解题路线

1. 建依赖邻接表和每个任务入度；所有入度为 0 的任务在时间 0 同时可开始，完成时刻为 1。
2. Kahn 拓扑遍历每条 u→v 时，令 finish[v]=max(finish[v],finish[u]+1)；当 v 所有依赖释放后，其 finish 即最早完成时刻。
3. 最终答案是 max finish，即 DAG 最长依赖路径的节点数；无限并行时任何调度都不能短于这条关键路径，而 ASAP 并行执行达到该下界。

手动走一遍

四个任务，依赖 0→2、1→2、2→3。0 与 1 可在第 0–1 单位同时做，2 在第 1–2 单位做，3 在第 2–3 单位做；虽然共有四个任务，最短完工时间为 3。

Python 参考实现

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

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

"""Minimum finish time of unit-duration DAG tasks with unlimited workers."""

from collections import deque


def minimum_makespan(task_count: int, dependencies: list[tuple[int, int]]) -> int:
    if task_count < 0:
        raise ValueError("task count must be nonnegative")
    graph = [set() for _ in range(task_count)]
    indegree = [0] * task_count
    for before, after in dependencies:
        if not (0 <= before < task_count and 0 <= after < task_count):
            raise ValueError("invalid task ID")
        if after not in graph[before]:
            graph[before].add(after)
            indegree[after] += 1
    ready = deque(i for i, degree in enumerate(indegree) if degree == 0)
    finish = [1] * task_count
    processed = 0
    while ready:
        task = ready.popleft()
        processed += 1
        for next_task in graph[task]:
            finish[next_task] = max(finish[next_task], finish[task] + 1)
            indegree[next_task] -= 1
            if indegree[next_task] == 0:
                ready.append(next_task)
    if processed != task_count:
        raise ValueError("dependency graph has a cycle")
    return max(finish, default=0)

复杂度

设 n 个任务、m 条不同依赖。建图和拓扑 DP 为 O(n+m) 时间、O(n+m) 空间；若用集合去重，哈希操作期望 O(1)。

易错点与追问

容易失分的边界

• 把全部任务数当答案会忽略并行；只算拓扑层数但漏掉某节点多个父依赖的最大完成时间也会错。
• 有环时 ready 队列会提前耗尽；必须检查实际处理任务数是否等于 n。
• 本题无限并行，与 q21 Metric Scheduler 高层任务必须串行的资源限制不同，不能直接套同一完工时间公式。

继续深挖

• 若每任务耗时 d[v] 不同，转移改为 finish[v]=max(finish[u])+d[v]，仍是 DAG 最长加权路径。
• 若机器数量有限，关键路径只是下界，任务调度会涉及资源竞争；需要明确优化目标和机器约束。