Parallel Courses III
Problem
Each course i takes time[i] months and may have prerequisites. You can take any number of courses in parallel as long as their prerequisites are finished. Return the minimum months to complete all courses.
n=3, relations=[[1,3],[2,3]], time=[3,2,5]8from collections import deque
def minimum_time(n, relations, time):
g = [[] for _ in range(n + 1)]
indeg = [0] * (n + 1)
for u, v in relations:
g[u].append(v)
indeg[v] += 1
dp = [0] * (n + 1)
q = deque()
for i in range(1, n + 1):
if indeg[i] == 0:
dp[i] = time[i - 1]
q.append(i)
while q:
u = q.popleft()
for v in g[u]:
dp[v] = max(dp[v], dp[u] + time[v - 1])
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
return max(dp)function minimumTime(n, relations, time) {
const g = Array.from({ length: n + 1 }, () => []);
const indeg = new Array(n + 1).fill(0);
for (const [u, v] of relations) { g[u].push(v); indeg[v]++; }
const dp = new Array(n + 1).fill(0);
const q = [];
for (let i = 1; i <= n; i++) {
if (indeg[i] === 0) { dp[i] = time[i - 1]; q.push(i); }
}
while (q.length) {
const u = q.shift();
for (const v of g[u]) {
dp[v] = Math.max(dp[v], dp[u] + time[v - 1]);
if (--indeg[v] === 0) q.push(v);
}
}
return Math.max(...dp);
}class Solution {
public int minimumTime(int n, int[][] relations, int[] time) {
java.util.List<java.util.List<Integer>> g = new java.util.ArrayList<>();
for (int i = 0; i <= n; i++) g.add(new java.util.ArrayList<>());
int[] indeg = new int[n + 1];
for (int[] r : relations) { g.get(r[0]).add(r[1]); indeg[r[1]]++; }
int[] dp = new int[n + 1];
java.util.Deque<Integer> q = new java.util.ArrayDeque<>();
for (int i = 1; i <= n; i++) {
if (indeg[i] == 0) { dp[i] = time[i - 1]; q.offer(i); }
}
int ans = 0;
while (!q.isEmpty()) {
int u = q.poll();
ans = Math.max(ans, dp[u]);
for (int v : g.get(u)) {
dp[v] = Math.max(dp[v], dp[u] + time[v - 1]);
if (--indeg[v] == 0) q.offer(v);
}
}
return ans;
}
}int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) {
vector<vector<int>> g(n + 1);
vector<int> indeg(n + 1, 0);
for (auto& r : relations) { g[r[0]].push_back(r[1]); indeg[r[1]]++; }
vector<int> dp(n + 1, 0);
queue<int> q;
for (int i = 1; i <= n; i++) if (indeg[i] == 0) { dp[i] = time[i - 1]; q.push(i); }
int ans = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
ans = max(ans, dp[u]);
for (int v : g[u]) {
dp[v] = max(dp[v], dp[u] + time[v - 1]);
if (--indeg[v] == 0) q.push(v);
}
}
return ans;
}Explanation
Because you can take courses in parallel, the total time is set by the longest chain of prerequisites — the slowest path through the dependency graph. We compute, for every course, the earliest month it can finish, and the answer is the largest of those.
We process courses in topological order using Kahn's algorithm: courses with no remaining prerequisites go into a queue first. A dp[v] array stores the finish time of course v. Courses with no prerequisites start at dp[v] = time[v].
When we pop a course u, we relax each edge u → v with dp[v] = max(dp[v], dp[u] + time[v-1]). This says course v cannot start until every prerequisite is done, so it waits for the slowest one. As each v loses its last prerequisite (indeg hits 0) it joins the queue.
The final answer is max(dp), the finish time of whichever course ends last.
Example: n=3, relations [[1,3],[2,3]], time=[3,2,5]. Courses 1 and 2 finish at 3 and 2. Course 3 waits for the max, which is 3, then adds its own 5 → dp[3] = 8. Answer is 8.