Parallel Courses III - Algorithm

$1.$ Build the adjacency list and in-degree array from relations. For each $[prev, next]$, add edge $prev \to next$ and increment indegree[next].

$2.$ Initialize finishTime[i] = time[i] for every course. Courses with no prerequisites finish in time[i] months.

$3.$ Push all courses with $indegree = 0$ into the queue and run Kahn's algorithm.

$4.$ When processing course $u$, for each neighbor $v$: set finishTime[v] = max(finishTime[v], finishTime[u] + time[v]). This propagates the earliest start.

$5.$ The answer is max(finishTime[i]) over all courses. This runs in $O(V + E)$ time and uses $O(V + E)$ space.