Parallel Courses III
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^40 <= relations.length <= min(n * (n - 1) / 2, 5 * 10^4)relations[j] = [prev, next]with1 <= prev, next <= nandprev != next- All pairs in
relationsare distinct, and the prerequisite graph has no cycle. time.length == nand1 <= 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.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
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.
| Approach | Time | Space |
|---|---|---|
| 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)
O(n · m)The longest prerequisite chain has at most n courses, so at most n sweeps over m relations are needed.O(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.
- Set
finish[c] = time[c - 1]for every course. - Sweep every relation
[p, c]: iffinish[p] + time[c - 1] > finish[c], raisefinish[c]and remember that something changed. - Repeat the sweep until a full pass changes nothing.
- 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;
}
}class Solution:
def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:
finish = [0] * (n + 1)
for c in range(1, n + 1):
finish[c] = time[c - 1]
changed = True
while changed:
changed = False
for p, c in relations:
cand = finish[p] + time[c - 1]
if cand > finish[c]:
finish[c] = cand
changed = True
return max(finish[1:])class Solution {
public:
int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) {
vector<int> finish(n + 1, 0);
for (int c = 1; c <= n; c++) finish[c] = time[c - 1];
bool changed = true;
while (changed) {
changed = false;
for (auto& 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 = max(best, finish[c]);
return best;
}
};function minimumTime(n, relations, time) {
const finish = new Array(n + 1).fill(0);
for (let c = 1; c <= n; c++) finish[c] = time[c - 1];
let changed = true;
while (changed) {
changed = false;
for (const [p, c] of relations) {
const cand = finish[p] + time[c - 1];
if (cand > finish[c]) {
finish[c] = cand;
changed = true;
}
}
}
let best = 0;
for (let c = 1; c <= n; c++) best = Math.max(best, finish[c]);
return best;
}2Optimal (Kahn's topological order + DP)
O(n + m)Every course is popped once and every relation is followed once.O(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.
- Build adjacency lists
prev -> nextand the in-degree of every course. - Push every course with in-degree 0 into a queue; their
startis 0. - Pop a course
c, computedone = start[c] + time[c - 1]and update the answer. - For each
nextofc: setstart[next] = max(start[next], done), decrement its in-degree and push it when it reaches 0. - 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;
}
}class Solution:
def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:
adj = [[] for _ in range(n + 1)]
indeg = [0] * (n + 1)
for p, c in relations:
adj[p].append(c)
indeg[c] += 1
start = [0] * (n + 1)
q = deque(c for c in range(1, n + 1) if indeg[c] == 0)
best = 0
while q:
c = q.popleft()
done = start[c] + time[c - 1]
best = max(best, done)
for nx in adj[c]:
start[nx] = max(start[nx], done)
indeg[nx] -= 1
if indeg[nx] == 0:
q.append(nx)
return bestclass Solution {
public:
int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) {
vector<vector<int>> adj(n + 1);
vector<int> indeg(n + 1, 0);
for (auto& r : relations) {
adj[r[0]].push_back(r[1]);
indeg[r[1]]++;
}
vector<int> start(n + 1, 0);
queue<int> q;
for (int c = 1; c <= n; c++) if (indeg[c] == 0) q.push(c);
int best = 0;
while (!q.empty()) {
int c = q.front();
q.pop();
int done = start[c] + time[c - 1];
best = max(best, done);
for (int nx : adj[c]) {
start[nx] = max(start[nx], done);
if (--indeg[nx] == 0) q.push(nx);
}
}
return best;
}
};function minimumTime(n, relations, time) {
const adj = Array.from({ length: n + 1 }, () => []);
const indeg = new Array(n + 1).fill(0);
for (const [p, c] of relations) {
adj[p].push(c);
indeg[c]++;
}
const start = new Array(n + 1).fill(0);
const q = [];
for (let c = 1; c <= n; c++) if (indeg[c] === 0) q.push(c);
let best = 0;
for (let head = 0; head < q.length; head++) {
const c = q[head];
const done = start[c] + time[c - 1];
best = Math.max(best, done);
for (const nx of adj[c]) {
start[nx] = Math.max(start[nx], done);
if (--indeg[nx] === 0) q.push(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.