Command Palette

Search for a command to run...

Hectal
Problem 24.4 · Topological SortHard

Parallel Courses III

PatternTopological Sort1D Dynamic Programming

What it teaches: DP in topological order: earliest finish = own time + latest prerequisite finish.

Practise it on judges as “Parallel Courses III”.

The problem

Courses 1..n take time[i − 1] months each; [prev, next] relations must be respected; any number of courses can run at once. Return the minimum months to finish all courses. The graph is a DAG.

Example 1

Input: n = 5, relations = [[1,5],[2,5],[3,5],[3,4],[4,5]], time = [1,2,3,4,5]
Output: 12

3 (3 months) → 4 (finishes at 7) → 5 (finishes at 12).

Constraints

  • 1 ≤ n ≤ 5 × 10⁴

Pattern clues in the wording

  • → Durations + dependencies
  • → Critical path

These clues point to Topological Sort: Order the nodes of a directed graph so every edge goes from earlier to later, by repeatedly taking nodes with no remaining prerequisites.

Stuck? Take one hint at a time

Solution.java · starter
import java.util.*;

class Solution {
    public int minimumTime(int n, int[][] relations, int[] time) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
n = 3
relations = [[1,3],[2,3]]
time = [3,2,5]
8
2
n = 5
relations = [[1,5],[2,5],[3,5],[3,4],[4,5]]
time = [1,2,3,4,5]
12

From slow to fast

Approaches

1. Kahn's with earliest start · O(n + E)
1

Kahn's with earliest start

Time O(n + E) Space O(n + E)

When popping u, finish[u] = start[u] + time[u]; for each successor v, start[v] = max(start[v], finish[u]). The answer is the largest finish.

Approach 1
import java.util.*;

class Solution {
    public int minimumTime(int n, int[][] relations, int[] time) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
        int[] indeg = new int[n + 1], start = new int[n + 1];
        for (int[] r : relations) { adj.get(r[0]).add(r[1]); indeg[r[1]]++; }
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 1; i <= n; i++) if (indeg[i] == 0) q.offer(i);
        int best = 0;
        while (!q.isEmpty()) {
            int u = q.poll();
            int finish = start[u] + time[u - 1];
            best = Math.max(best, finish);
            for (int v : adj.get(u)) {
                start[v] = Math.max(start[v], finish);
                if (--indeg[v] == 0) q.offer(v);
            }
        }
        return best;
    }
}

Verdict: The critical path method from project management.

Before you submit

Edge cases and common mistakes

Test these inputs

  • No relations (max of times)
  • Long chain

Mistakes people make

  • Summing all times (ignores parallelism).

Interview

Follow-up questions

How do you find which courses are critical (any delay delays everything)?