Parallel Courses III

Hard Graphs Topological Sort Original on LeetCode

Reported atStripeSnowflake

Parallel Courses III is a hard graphs problem solved with the topological sort pattern. The best approach, optimal (kahn's topological order + dp), runs in O(n + m) time and O(n + m) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (relax until nothing changes) up.

Problem

There are n courses labelled 1 to n. Each pair relations[j] = [prev, next] means course prev must be finished before course next can begin. Course i takes exactly time[i - 1] months to complete.

You may work on any number of courses at the same time, and a course can start the moment all of its prerequisites are done. Return the minimum number of months needed to finish every course. The prerequisite graph is guaranteed to have no cycle.

Examples

Example 1

Input
n = 4, relations = [[1, 2], [1, 3], [2, 4], [3, 4]], time = [2, 5, 1, 3]
Output
10
Why
Course 1 ends at 2, course 2 at 7, course 3 at 3; course 4 waits for the later one (7) and ends at 10.

Example 2

Input
n = 3, relations = [], time = [4, 9, 2]
Output
9
Why
With no prerequisites all three run in parallel, so the longest one decides the total.

Example 3

Input
n = 5, relations = [[1, 3], [2, 3], [3, 5], [4, 5]], time = [6, 1, 2, 10, 1]
Output
11
Why
Course 3 can start at 6 and ends at 8, course 4 ends at 10, so course 5 starts at 10 and ends at 11.

Constraints

  • 1 <= n <= 5 * 10^4
  • 0 <= relations.length <= min(n * (n - 1) / 2, 5 * 10^4)
  • relations[j] = [prev, next] with 1 <= prev, next <= n and prev != next
  • All pairs in relations are distinct, and the prerequisite graph has no cycle.
  • time.length == n and 1 <= time[i] <= 10^4

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (relax until nothing changes)O(n · m)O(n)
Optimal (Kahn's topological order + DP)O(n + m)O(n + m)

1Brute force (relax until nothing changes)

TimeO(n · m)The longest prerequisite chain has at most n courses, so at most n sweeps over m relations are needed.
SpaceO(n)One array of finish times.

Start every course's finish time at its own duration. Repeatedly sweep all relations and push each course's finish time up to finish[prev] + time[next] when that is larger. Because the graph has no cycle, the values stop changing after at most n sweeps, like Bellman-Ford for longest paths.

  1. Set finish[c] = time[c - 1] for every course.
  2. Sweep every relation [p, c]: if finish[p] + time[c - 1] > finish[c], raise finish[c] and remember that something changed.
  3. Repeat the sweep until a full pass changes nothing.
  4. Return the maximum of finish.
class Solution {
    public int minimumTime(int n, int[][] relations, int[] time) {
        int[] finish = new int[n + 1];
        for (int c = 1; c <= n; c++) finish[c] = time[c - 1];
        boolean changed = true;
        while (changed) {
            changed = false;
            for (int[] r : relations) {
                int cand = finish[r[0]] + time[r[1] - 1];
                if (cand > finish[r[1]]) {
                    finish[r[1]] = cand;
                    changed = true;
                }
            }
        }
        int best = 0;
        for (int c = 1; c <= n; c++) best = Math.max(best, finish[c]);
        return best;
    }
}

2Optimal (Kahn's topological order + DP)

TimeO(n + m)Every course is popped once and every relation is followed once.
SpaceO(n + m)Adjacency lists hold m edges, plus a few arrays of size n and the queue.

Process courses in topological order with Kahn's algorithm. Keep start[c], the latest finish time among the prerequisites seen so far. When a course is popped, all of its prerequisites are done, so its finish time is start[c] + time[c]; pass that value to every course that depends on it.

  1. Build adjacency lists prev -> next and the in-degree of every course.
  2. Push every course with in-degree 0 into a queue; their start is 0.
  3. Pop a course c, compute done = start[c] + time[c - 1] and update the answer.
  4. For each next of c: set start[next] = max(start[next], done), decrement its in-degree and push it when it reaches 0.
  5. Return the largest finish time seen.
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];
        for (int[] r : relations) {
            adj.get(r[0]).add(r[1]);
            indeg[r[1]]++;
        }
        int[] start = new int[n + 1];
        Deque<Integer> q = new ArrayDeque<>();
        for (int c = 1; c <= n; c++) if (indeg[c] == 0) q.add(c);
        int best = 0;
        while (!q.isEmpty()) {
            int c = q.poll();
            int done = start[c] + time[c - 1];
            best = Math.max(best, done);
            for (int nx : adj.get(c)) {
                start[nx] = Math.max(start[nx], done);
                if (--indeg[nx] == 0) q.add(nx);
            }
        }
        return best;
    }
}

Edge cases to test

  • No relations: the answer is the largest single duration
  • One long chain: the answer is the sum of all durations
  • A course with several prerequisites must wait for the one that finishes last, not the one with the most courses before it
  • A short chain of long courses can beat a long chain of short courses

Hints

Hint 1

A course can start only when its slowest prerequisite has finished. Its finish time is that moment plus its own duration.

Hint 2

Define finish[c] = time[c] + max(finish[p]) over all prerequisites p of c. The answer is the largest finish value.

Hint 3

Compute finish in topological order (Kahn's algorithm): when a course's in-degree drops to zero, all of its prerequisites already have final finish times.

FAQ

What is the best time complexity for Parallel Courses III?

Optimal (Kahn's topological order + DP) runs in O(n + m) time and O(n + m) extra space. Every course is popped once and every relation is followed once.

Which pattern does Parallel Courses III use?

It is a graphs problem that uses the topological sort pattern. Other problems with the same pattern: Topological sort using BFS, Course Schedule, Course Schedule II.

Is there a brute force solution for Parallel Courses III?

Yes. Brute force (relax until nothing changes) takes O(n · m) time and O(n) space. Start every course's finish time at its own duration.

Which edge cases should I test for Parallel Courses III?

No relations: the answer is the largest single duration; One long chain: the answer is the sum of all durations; A course with several prerequisites must wait for the one that finishes last, not the one with the most courses before it; A short chain of long courses can beat a long chain of short courses.