Parallel Courses III
HardPrompt
You are given an integer n, which indicates that there are n courses labeled from 1 to n. You are also given a 2D integer array relations where relations[j] = [prevCoursej, nextCoursej] denotes that course prevCoursej has to be completed before course nextCoursej (prerequisite relationship). Furthermore, you are given a 0-indexed integer array time where time[i] denotes how many months it takes to complete the (i+1)th course.
You must find the minimum number of months needed to complete all the courses following these rules:
- You may start taking a course at any time if the prerequisites are met.
- Any number of courses can be taken at the same time.
Return the minimum number of months needed to complete all the courses.
Note: The test cases are generated such that it is possible to complete every course (i.e., the graph is a directed acyclic graph).
Example 1:
Input: n = 3, relations = [[1,3],[2,3]], time = [3,2,5]
Output: 8
Explanation: The figure above represents the given graph and the time required to complete each course.
We start course 1 and course 2 simultaneously at month 0.
Course 1 takes 3 months and course 2 takes 2 months to complete respectively.
Thus, the earliest time we can start course 3 is at month 3, and the total time required is 3 + 5 = 8 months.Example 2:
Input: n = 5, relations = [[1,5],[2,5],[3,5],[3,4],[4,5]], time = [1,2,3,4,5]
Output: 12
Explanation: The figure above represents the given graph and the time required to complete each course.
You can start courses 1, 2, and 3 at month 0.
You can complete them after 1, 2, and 3 months respectively.
Course 4 can be taken only after course 3 is completed, i.e., after 3 months. It is completed after 3 + 4 = 7 months.
Course 5 can be taken only after courses 1, 2, 3, and 4 have been completed, i.e., after max(1,2,3,7) = 7 months.
Thus, the minimum time needed to complete all the courses is 7 + 5 = 12 months.
Constraints:
1 <= n <= 5 * 1040 <= relations.length <= min(n * (n - 1) / 2, 5 * 104)relations[j].length == 21 <= prevCoursej, nextCoursej <= nprevCoursej != nextCoursej- All the pairs
[prevCoursej, nextCoursej]are unique. time.length == n1 <= time[i] <= 104- The given graph is a directed acyclic graph.
Approaches
2 approaches with complexity analysis and trade-offs.
This problem can be framed as finding the longest path in a Directed Acyclic Graph (DAG), where the 'weight' of each node is the time required to complete the corresponding course. A recursive Depth-First Search (DFS) approach is a natural way to solve this. To prevent recomputing the completion time for the same course multiple times, which would lead to an exponential time complexity, we use memoization to store and reuse the results.
Algorithm
- Build a prerequisite graph (adjacency list
prereqGraph) whereprereqGraph[i]contains the list of prerequisites for coursei. - Initialize a memoization array
memoof sizen+1to store the calculated longest path (completion time) for each course. - Iterate through each course from 1 to
n. For each coursei, call a recursive helper functiondfs(i, prereqGraph, time, memo). - The
dfsfunction:- If
memo[course]is already computed, return it. - Find the maximum completion time among all prerequisites by recursively calling
dfson them. Let this bemaxPrereqTime. - The completion time for the current course is
maxPrereqTime + time[course - 1]. - Store this result in
memo[course]and return it.
- If
- After the loop, the overall minimum time is the maximum value found across all DFS calls.
Walkthrough
In this top-down dynamic programming approach, we define a function, say dfs(course), which calculates the minimum time required to complete that course and all of its prerequisites.
- The base case for the recursion is a course with no prerequisites. Its completion time is simply its own
time. - For a course with prerequisites, its start time is determined by the prerequisite that finishes last. So,
startTime(course) = max(completionTime(prereq))for all its prerequisites. - The completion time for the course is then
startTime(course) + time(course).
We use a memoization array, memo, to store the calculated completion times. Before computing dfs(course), we check if memo[course] has a stored value. If so, we return it immediately. Otherwise, we compute the value, store it in memo, and then return it.
To implement this, we first need to build a graph representation that allows us to easily find the prerequisites for any given course. An adjacency list where prereqGraph[i] stores the list of prerequisites for course i is suitable. The final answer is the maximum completion time among all courses.
import java.util.ArrayList;import java.util.List; class Solution { public int minimumTime(int n, int[][] relations, int[] time) { List<List<Integer>> prereqGraph = new ArrayList<>(); for (int i = 0; i <= n; i++) { prereqGraph.add(new ArrayList<>()); } for (int[] relation : relations) { // relation[0] is a prereq for relation[1] prereqGraph.get(relation[1]).add(relation[0]); } int[] memo = new int[n + 1]; int maxTotalTime = 0; for (int i = 1; i <= n; i++) { maxTotalTime = Math.max(maxTotalTime, dfs(i, prereqGraph, time, memo)); } return maxTotalTime; } private int dfs(int course, List<List<Integer>> prereqGraph, int[] time, int[] memo) { if (memo[course] != 0) { return memo[course]; } int maxPrereqTime = 0; for (int prereq : prereqGraph.get(course)) { maxPrereqTime = Math.max(maxPrereqTime, dfs(prereq, prereqGraph, time, memo)); } // The time to complete this course is its own time plus the time of the longest prerequisite path. memo[course] = maxPrereqTime + time[course - 1]; return memo[course]; }}Complexity
Time
O(V + E), where V is the number of courses (n) and E is the number of relations. Building the graph takes `O(E)`. The DFS function with memoization ensures that each course (node) and prerequisite relationship (edge) is processed exactly once.
Space
O(V + E), where V is the number of courses (n) and E is the number of relations. This is for storing the adjacency list (`O(V + E)`), the memoization array (`O(V)`), and the recursion stack (`O(V)` in the worst case).
Trade-offs
Pros
Conceptually straightforward, as it directly translates the recursive nature of the problem.
Easy to implement once the graph representation is decided.
Cons
Recursive calls have slightly more overhead than an iterative approach.
Can lead to a
StackOverflowErroron very deep graphs, though the problem constraints make this less likely.
This is an iterative, bottom-up dynamic programming approach based on topological sorting (specifically, Kahn's algorithm). We process courses in an order such that all prerequisites of a course are processed before the course itself. This allows us to build up the completion times from the starting courses (those with no prerequisites) towards the final courses in the dependency chain.
Algorithm
- Build an adjacency list
adjand aninDegreearray from therelations.adj[u]will store courses that haveuas a prerequisite. - Initialize a queue and add all courses
iwithinDegree[i] == 0. - Initialize a
completionTimearray. For each courseiadded to the queue, setcompletionTime[i] = time[i-1]. - While the queue is not empty:
- Dequeue a course
u. - For each neighbor
vofu:- Update
completionTime[v] = max(completionTime[v], completionTime[u] + time[v-1]). - Decrement
inDegree[v]. - If
inDegree[v]becomes 0, enqueuev.
- Update
- Dequeue a course
- The result is the maximum value in the
completionTimearray.
Walkthrough
We first model the course dependencies as a directed graph. We need an adjacency list adj where adj[u] stores the list of courses that depend on u, and an inDegree array where inDegree[v] stores the number of prerequisites for course v. We also use a completionTime array to store the earliest possible completion time for each course.
The algorithm starts by identifying all courses with an in-degree of 0. These are the courses with no prerequisites. We add them to a queue and set their completionTime to their own time.
We then process the queue. For each course u we dequeue, we consider it 'completed'. We then look at all its successor courses v. For each v, we update its potential completion time. The start time for v must be at least completionTime[u]. Therefore, the completion time for v through the path from u is completionTime[u] + time[v-1]. Since v might have multiple prerequisites, we take the maximum of these potential completion times: completionTime[v] = max(completionTime[v], completionTime[u] + time[v-1]).
We also decrement the in-degree of v. If the in-degree of v becomes 0, it means all its prerequisites have been processed, so we can now add v to the queue. We continue this until the queue is empty. The overall minimum time to finish all courses is the maximum value in the completionTime array.
import java.util.ArrayList;import java.util.LinkedList;import java.util.List;import java.util.Queue; class Solution { public int minimumTime(int n, int[][] relations, int[] time) { List<List<Integer>> adj = new ArrayList<>(); int[] inDegree = new int[n + 1]; for (int i = 0; i <= n; i++) { adj.add(new ArrayList<>()); } for (int[] relation : relations) { int prev = relation[0]; int next = relation[1]; adj.get(prev).add(next); inDegree[next]++; } Queue<Integer> queue = new LinkedList<>(); int[] completionTime = new int[n + 1]; for (int i = 1; i <= n; i++) { if (inDegree[i] == 0) { queue.offer(i); completionTime[i] = time[i - 1]; } } while (!queue.isEmpty()) { int u = queue.poll(); for (int v : adj.get(u)) { completionTime[v] = Math.max(completionTime[v], completionTime[u] + time[v - 1]); inDegree[v]--; if (inDegree[v] == 0) { queue.offer(v); } } } int maxTotalTime = 0; for (int i = 1; i <= n; i++) { maxTotalTime = Math.max(maxTotalTime, completionTime[i]); } return maxTotalTime; }}Complexity
Time
O(V + E), where V is the number of courses (n) and E is the number of relations. Building the graph and in-degrees takes `O(V + E)`. The topological sort processes each node and edge once. Finding the max at the end takes `O(V)`.
Space
O(V + E), where V is the number of courses (n) and E is the number of relations. This space is used for the adjacency list (`O(V + E)`), the in-degree array (`O(V)`), the queue (`O(V)`), and the completion time array (`O(V)`).
Trade-offs
Pros
Iterative approach avoids recursion overhead and the risk of stack overflow.
Generally considered a very robust and efficient method for problems on DAGs.
The
completionTimearray directly computes the longest path to each node from the source nodes.
Cons
Requires building both an adjacency list and an in-degree array, which can be slightly more setup than the recursive approach.
Solutions
Solution
class Solution {public int minimumTime(int n, int[][] relations, int[] time) { List<Integer>[] g = new List[n]; Arrays.setAll(g, k->new ArrayList<>()); int[] indeg = new int[n]; for (int[] e : relations) { int a = e[0] - 1, b = e[1] - 1; g[a].add(b); ++indeg[b]; } Deque<Integer> q = new ArrayDeque<>(); int[] f = new int[n]; int ans = 0; for (int i = 0; i < n; ++i) { int v = indeg[i], t = time[i]; if (v == 0) { q.offer(i); f[i] = t; ans = Math.max(ans, t); } } while (!q.isEmpty()) { int i = q.pollFirst(); for (int j : g[i]) { f[j] = Math.max(f[j], f[i] + time[j]); ans = Math.max(ans, f[j]); if (--indeg[j] == 0) { q.offer(j); } } } return ans; }}class Solution {public: int minimumTime(int n, vector<vector<int>> &relations, vector<int> &time) { vector<vector<int>> g(n); vector<int> indeg(n); for (auto &e : relations) { int a = e[0] - 1, b = e[1] - 1; g[a].push_back(b); ++indeg[b]; } queue<int> q; vector<int> f(n); int ans = 0; for (int i = 0; i < n; ++i) { int v = indeg[i], t = time[i]; if (v == 0) { q.push(i); f[i] = t; ans = max(ans, t); } } while (!q.empty()) { int i = q.front(); q.pop(); for (int j : g[i]) { if (--indeg[j] == 0) { q.push(j); } f[j] = max(f[j], f[i] + time[j]); ans = max(ans, f[j]); } } return ans; }};class Solution: def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int: g = defaultdict(list) indeg = [0] * n for a, b in relations: g[a - 1]. append(b - 1) indeg[b - 1] += 1 q = deque() f = [0] * n ans = 0 for i, (v, t) in enumerate(zip(indeg, time)): if v == 0: q . append(i) f[i] = t ans = max(ans, t) while q: i = q . popleft() for j in g[i]: f[j] = max(f[j], f[i] + time[j]) ans = max(ans, f[j]) indeg[j] -= 1 if indeg[j] == 0: q . append(j) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.