题目重点：题目明确每批课程全部完成后才开下一批，给 [1,10,10,1] 返回 20；用 Kahn 分层解释与即时启动关键路径模型的区别。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 课程 ID 为 1…N，边 (a,b) 表示 b 需在 a 完成后修；同一批所有入度为 0 的待修课同时开始，下一批必须等待本批全部完成。
- 当前批耗时为该批最长 duration，各课耗时非负，课可无限并行；图有环返回 None 作为训练约定。
- 如果允许前置课一结束就立刻开启后续而无需等整批，计算变为 DAG 最长路径，不应混同本题。
解题路线
- 建立 successor 邻接表和入度；初始入度零课程构成第一批。
- 每轮固定本批队列长度，取出所有本批课程并加上其 duration 最大值；再释放后继的入度零节点供下一轮使用，不能在当前批中立即执行。
- 总处理节点数小于 N 则存在环或环依赖，返回无解；重复边若输入允许则按两次入度与邻接一致处理。
- 用独立集合模型反复扫描所有未完成课程，找其先修集合是否都在 done 中，随机图对照 10,000 组。
手动走一遍
1→2、3→4，duration=[1,10,10,1]。批 1 为 {1,3}，耗时 10；批 2 为 {2,4}，耗时 10；总计 20。若 1 完成后可立即开启 2，则路径 1→2 耗 11，路径 3→4 耗 11，总完工 11；这不是题目的批次规则。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Kahn layers: next course batch starts only after current batch completes."""
from collections import deque
def batch_course_time(durations: list[int], prerequisites: list[tuple[int, int]]) -> int | None:
n = len(durations)
if any(duration < 0 for duration in durations):
raise ValueError("negative duration")
successors = [[] for _ in range(n)]
indegree = [0] * n
for before, after in prerequisites:
if not 1 <= before <= n or not 1 <= after <= n:
raise ValueError("unknown course")
successors[before - 1].append(after - 1)
indegree[after - 1] += 1
ready = deque(i for i, degree in enumerate(indegree) if degree == 0)
processed = 0
elapsed = 0
while ready:
current_batch = [ready.popleft() for _ in range(len(ready))]
elapsed += max(durations[i] for i in current_batch)
for course in current_batch:
processed += 1
for nxt in successors[course]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
ready.append(nxt)
return elapsed if processed == n else None
复杂度
N 门课、E 条依赖边，构图和 Kahn 分层 O(N+E) 时间、O(N+E) 空间。批次耗时累加可能超过固定宽度整数，应选足够大的类型。
易错点与追问
容易失分的边界
- 释放某个后继后马上在同一批执行，把总时长错误算成 11。
- 只数批数，不加每批最长时长。
- 有环时队列空就直接返回累计值，漏报未完成课程。
- 用全图最长路径解替代明确的整批等待模型。
- 不确认边方向，先修课和后修课颠倒。
继续深挖
- 若课程允许即时启动，如何在 DAG 上求最早完成时刻？
- 若最多 K 门课并行，为什么简单 Kahn 层已不够？
- 某课程必须在限定窗口开课，状态如何变化？
