#2050 Parallel Courses III

frequently reported atGoogle Goldman Sachs Amazon

the problem

In plain words

Courses 1..n, relations[j] = [prev, next] means prev must finish before next starts, and course i takes time[i−1] months. Any number of courses can run at once. Return the minimum months to finish all courses (the graph is a DAG).

in n = 3, relations = [[1,3],[2,3]], time = [3,2,5]

out 8

1 and 2 run together; 3 starts at month 3 and ends at 8.

in n = 5, relations = [[1,5],[2,5],[3,5],[3,4],[4,5]], time = [1,2,3,4,5]

out 12

Critical path 3 → 4 → 5: 3 + 4 + 5.

1 ≤ n ≤ 5·10⁴
0 ≤ relations.length ≤ min(n·(n−1)/2, 5·10⁴)
1 ≤ time[i] ≤ 10⁴
The graph is a DAG

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternTopological sort & cycle detection DP on a DAG

finish[c] = time[c] + max(finish[p]) over prerequisites p. The answer is the heaviest chain — the critical path — which topological order computes in one pass.

solutions

From brute force to optimal

Recursively compute finish(c) from its prerequisites, caching results.

Store each course's prerequisite list.
finish(c) = time[c] + max finish(p), memoised.
Answer = max over all courses.

timeO(V + E)

Each course computed once; each relation read once.

spaceO(V + E)

Lists + memo + recursion depth up to V — risky at 5·10⁴ in Java.

javajava.util.*

1class Solution {2    public int minimumTime(int n, int[][] relations, int[] time) {3        List<List<Integer>> prereqs = new ArrayList<>();4        for (int i = 0; i < n; i++) prereqs.add(new ArrayList<>());5        for (int[] r : relations) prereqs.get(r[1] - 1).add(r[0] - 1); // course → its prerequisites6        int[] memo = new int[n]; // 0 = not computed yet (every finish time is ≥ 1)7        int answer = 0;8        for (int c = 0; c < n; c++) answer = Math.max(answer, finish(c, prereqs, time, memo));9        return answer;10    }11 12    /** Earliest month course c can finish = its own time + the latest prerequisite finish. */13    private int finish(int c, List<List<Integer>> prereqs, int[] time, int[] memo) {14        if (memo[c] != 0) return memo[c];15        int start = 0;16        for (int p : prereqs.get(c)) start = Math.max(start, finish(p, prereqs, time, memo));17        return memo[c] = start + time[c];18    }19}

Process courses in topological order; when a course is polled its finish time is final, so push it to its dependants.

Seed in-degree-0 courses with finish = time.
Poll u; answer = max(answer, finish[u]).
For each next v: finish[v] = max(finish[v], finish[u] + time[v]); enqueue when in-degree hits 0.

timeO(V + E)

Standard Kahn pass with O(1) work per edge.

spaceO(V + E)

Adjacency list, in-degree, finish arrays, queue.

javajava.util.*

1class Solution {2    public int minimumTime(int n, int[][] relations, int[] time) {3        List<List<Integer>> adj = new ArrayList<>();4        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());5        int[] indegree = new int[n];6        for (int[] r : relations) {7            adj.get(r[0] - 1).add(r[1] - 1); // 1-indexed input8            indegree[r[1] - 1]++;9        }10        int[] finish = new int[n]; // earliest finish month of each course11        Deque<Integer> queue = new ArrayDeque<>();12        for (int v = 0; v < n; v++) {13            if (indegree[v] == 0) { finish[v] = time[v]; queue.offer(v); }14        }15        int answer = 0;16        while (!queue.isEmpty()) {17            int u = queue.poll();18            answer = Math.max(answer, finish[u]);19            for (int v : adj.get(u)) {20                finish[v] = Math.max(finish[v], finish[u] + time[v]);21                if (--indegree[v] == 0) queue.offer(v);22            }23        }24        return answer;25    }26}

sim

Watch finish times flow along the DAG

loading simulation…

javajava.util.*

1class Solution {2    public int minimumTime(int n, int[][] relations, int[] time) {3        List<List<Integer>> adj = new ArrayList<>();4        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());5        int[] indegree = new int[n];6        for (int[] r : relations) {7            adj.get(r[0] - 1).add(r[1] - 1); // 1-indexed input8            indegree[r[1] - 1]++;9        }10        int[] finish = new int[n]; // earliest finish month of each course11        Deque<Integer> queue = new ArrayDeque<>();12        for (int v = 0; v < n; v++) {13            if (indegree[v] == 0) { finish[v] = time[v]; queue.offer(v); }14        }15        int answer = 0;16        while (!queue.isEmpty()) {17            int u = queue.poll();18            answer = Math.max(answer, finish[u]);19            for (int v : adj.get(u)) {20                finish[v] = Math.max(finish[v], finish[u] + time[v]);21                if (--indegree[v] == 0) queue.offer(v);22            }23        }24        return answer;25    }26}

in the room

How to say it in the interview

talk track

Spot it: unlimited parallelism → only dependency chains matter → longest path in a DAG.
Explain why topological order makes the DP valid: every prerequisite is final before it's used.
Mention Java recursion depth as the reason to prefer Kahn here.

traps

Adding up every course's time — courses run in parallel, so only the heaviest chain counts.
Mixing indexes: relations use courses 1..n, but time[] is 0-based, so course c takes time[c − 1].
Returning the finish time of the last course polled — the answer is the max over all courses.

what they ask next

Follow-ups

At most k courses per semester (LC 1494)?

The greedy/critical-path idea breaks; it needs bitmask DP.

Unit time, count semesters (LC 1136, Premium)?

Count Kahn layers (BFS levels); return −1 on a cycle.

before you submit

Edge cases to test

No relations → the answer is the largest single time.
Courses are 1-based in relations, but time[] is 0-based.
One long chain: recursion would go n deep (up to 5·10⁴) — Kahn stays a loop.

practise next