← DSA Atlas
Dedicated problem page · #2050

Parallel Courses III

HardTopological SortTopological longest path (critical path)Kahn's BFS topological sort + DP
Solve on LeetCode ↗
2050
HardTopological SortKahn's BFS topological sort + DPTopological longest path (critical path)

Parallel Courses III

You are given an integer n (courses labeled 1..n), a list of prerequisite pairs relations where [a, b] means course a must finish before course b starts, and an array time where time[i] is the months course i+1 takes. Any number of courses may run in parallel, and a course may begin the instant all its prerequisites are done. Return the minimum number of months to complete all courses. The graph is guaranteed to be a DAG.

Open official problem prompt ↗
In plain English

Find the minimum wall-clock months to finish all courses when every course can run in parallel but must wait for its prerequisites — i.e. the length of the longest weighted dependency chain.

Picture it like this

Think of a construction project: many crews work simultaneously, but the roof crew cannot start until the walls are up and the walls cannot start until the foundation cures. The whole build takes as long as the slowest chain of dependent tasks — the critical path — not the sum of every task.

Example
Input
n = 3, relations = [[1,3],[2,3]], time = [3,2,5]
Output
8
Why
Courses 1 (3mo) and 2 (2mo) run in parallel from month 0; course 3 waits for both, so it starts at month 3 and finishes at 3 + 5 = 8.
Constraints
1 <= n <= 5 * 10^40 <= relations.length <= min(n * (n - 1) / 2, 5 * 10^4)relations[j].length == 21 <= prevCourse_j, nextCourse_j <= nprevCourse_j != nextCourse_jAll the pairs [prevCourse_j, nextCourse_j] are uniquetime.length == n1 <= time[i] <= 10^4The given graph is a directed acyclic graph
Pattern lesson

See the pattern, then code

Topological longest path (critical path)
Recognition clue

Dependencies plus unlimited parallelism and a 'minimum total time' target is the signature of a critical-path (longest-path) query over a DAG.

↗
Topological Sort

Prerequisites, dependencies, build order, or scheduling over a DAG.. With unlimited parallelism, a course's earliest finish is its own duration plus the latest finish among its prerequisites. Processing nodes in topological order guarantees every prerequisite's finish time is final before the course is evaluated, so a single pass computes exact finish times.

New words, made simpleKnow these before the algorithm
DAG
Directed acyclic graph — dependencies with no cycles, so a valid ordering always exists.
Indegree
How many prerequisites a course still has unmet.
Finish time
The earliest month a course can be completed given its dependency chain.
Critical path
The longest chain of dependent durations; its length is the answer.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Enumerate all dependency paths

The number of paths can blow up exponentially in a dense DAG; infeasible for n up to 5*10^4.

List every path from a source to a sink, sum durations along each, and take the maximum.

Time O(exponential)Space O(n)
Best choiceTopological sort with finish-time DP (Kahn)

One linear pass computes exact finish times because prerequisites are always resolved first.

Process courses in dependency order; each course's finish time is its duration plus the max finish time of its prerequisites.

Time O(n + e)Space O(n + e)
The rule we keep true

Invariant

When a course is dequeued, finish[course] already equals its true earliest completion time, because every prerequisite was processed (and relaxed into it) before its indegree hit zero.

Why this is correct

Reasoning

Kahn's order visits a node only after all incoming edges are consumed, so every term feeding into max(finish[prereq]) is final. Adding the course's own duration then yields its exact earliest finish; the global answer is the largest such value, which equals the critical-path length.

The algorithm in three movesSay these aloud before coding
1Build the adjacency list and indegree array from relations

finish[1]=3, finish[2]=2

2Seed a queue with every course that has no prerequisites, setting its finish time to its own duration

finish[3]=max(3+5, 2+5)=8

3Pop a course, relax each successor: finish[next] = max(finish[next], finish[cur] + time[next])

answer=max(3,2,8)=8

4Decrement the successor's indegree and enqueue it once it reaches zero

5Return the maximum finish time over all courses

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
C1:30
C2:21
C3:52
1 · Readrelations [[1,3],[2,3]], time [3,2,5]
2 · AskWhich courses have no prerequisites?
3 · Update stateindeg = [_,0,0,2]; finish = [_,3,2,0]
4 · ResultCourses 1 and 2 enqueued with finish 3 and 2
Key takeaway

Courses 1 and 2 start together; course 3 is gated by the later of the two and finishes at month 8.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 4-9Build graph and indegrees

    Adjacency list points prerequisites at their dependents; indegree counts unmet prerequisites per course.

  2. 2
    Lines 10-15Seed sources

    Courses with no prerequisites can start at month 0, so their finish time is just their own duration; they enter the queue.

  3. 3
    Lines 16-23Relax in topological order

    Each successor's finish time is pushed to the max of its current value and this course's finish plus the successor's duration; it enqueues only when fully unlocked.

  4. 4
    Lines 24Global maximum

    The answer is the latest finish time across all courses — the critical-path length.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • relations is empty: every course is independent, so the answer is max(time)
  • A single long chain 1->2->...->n: answer is the sum of all durations
  • A course that is both a prerequisite and a dependent (interior node) must aggregate the max over all its prerequisites
  • n = 1 with no relations: answer is time[0]
!

Common beginner mistakes

  • Indexing time with the 1-based course label directly — remember time is 0-indexed, so use time[course - 1]
  • Summing prerequisite finish times instead of taking the max; parallelism means only the latest prerequisite gates the start
  • Returning finish of the last dequeued node rather than the max over all nodes — multiple sinks can exist
  • Using plain recursion/DFS without memoization, which recomputes shared subpaths and can hit recursion limits at n = 5*10^4
Check your understanding

Why can we take the maximum (not the sum) of prerequisite finish times when computing a course's start?

More in Topological Sort

#207Course ScheduleCycle detection by peeling zero in-degree nodes#210Course Schedule IIEmit nodes in dependency-safe order#269Alien DictionaryDerive edges from adjacent-item comparisons, then topologically sort#310Minimum Height TreesTrim leaves inward until the center remains#329Longest Increasing Path in a MatrixLongest path in an implicit DAG via memoized DFS#1203Sort Items by Groups Respecting DependenciesTwo-level topological sort (order groups, then items within groups)