Parallel Courses III
Problem
Given n courses labeled from 1 to n, an array relations where relations[i] = [prevCourse, nextCourse] denotes that prevCourse must be completed before nextCourse, and an array time where time[i] is the time to complete the (i+1)th course, return the minimum number of weeks to complete all courses.
- 1 ≤ n ≤ 5 * 10⁴
- 0 ≤ relations.length ≤ min(n * (n - 1) / 2, 5 * 10⁴)
- relations[i].length == 2
- 1 ≤ prevCourse, nextCourse ≤ n
- prevCourse != nextCourse
- All prerequisite pairs are unique
- time.length == n
- 1 ≤ time[i] ≤ 10⁴
Example
n = 3, relations = [[1,3],[2,3]], time = [3,2,5]8Courses 1 and 2 have no prerequisites and can be taken simultaneously, taking 3 and 2 weeks respectively. Course 3 depends on both and takes 5 weeks. The earliest course 3 can start is after max(3,2) = 3 weeks, so total time is 3 + 5 = 8 weeks.
Approach
Straightforward Solution
A naive approach might attempt to simulate all possible course schedules or use DFS to compute completion times, but without memoization or topological ordering, this can be inefficient or complicated.
Core Observation
The problem models a directed acyclic graph where nodes represent courses and edges represent prerequisite dependencies. The minimum completion time for each course depends on the maximum completion time among its prerequisites plus its own duration.
Path to Optimal
Recognizing the problem as a DAG with dependencies suggests using topological sort to process courses in order of prerequisites. By maintaining an indegree array and a queue of courses with zero prerequisites, the algorithm can iteratively compute the earliest completion time for each course by taking the maximum completion time of its prerequisites plus its own time. This approach ensures each course is processed once, and dependencies are respected.
Optimal Approach
Build the graph and indegree array from relations. Initialize a queue with courses having zero indegree (no prerequisites) and set their completion times to their own durations. Then, process the queue: for each course, update the completion time of its neighbors to the maximum of their current completion time and the current course's completion time plus the neighbor's duration. Decrement indegrees and enqueue neighbors when their indegree reaches zero. The answer is the maximum completion time among all courses.
Time
O(n + m)
Building the graph and indegree array takes O(m) where m is the number of relations. The BFS traversal processes each node and edge once, resulting in O(n + m) total time.
Space
O(n + m)
The adjacency list stores all edges (O(m)) and the indegree and dp arrays store information for each course (O(n)). This space is necessary to represent the graph and track completion times.
Pattern Spotlight
Topological Sort (Dependency Resolution with DP)
When scheduling tasks with prerequisites, use topological sort to process tasks in dependency order, and propagate the maximum completion time through the graph to find the earliest finish time for all tasks.
Solution
| 1 | class Solution: |
| 2 | def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int: |
| 3 | graph = defaultdict(list) |
| 4 | indegree = [0] * (n + 1) |
| 5 | |
| 6 | for u, v in relations: |
| 7 | graph[u].append(v) |
| 8 | indegree[v] += 1 |
| 9 | |
| 10 | q = deque() |
| 11 | dp = [0] * (n + 1) |
| 12 | |
| 13 | for i in range(1, n + 1): |
| 14 | if indegree[i] == 0: |
| 15 | q.append(i) |
| 16 | dp[i] = time[i - 1] |
| 17 | |
| 18 | while q: |
| 19 | course = q.popleft() |
| 20 | |
| 21 | for nei in graph[course]: |
| 22 | dp[nei] = max(dp[nei], dp[course] + time[nei - 1]) |
| 23 | indegree[nei] -= 1 |
| 24 | |
| 25 | if indegree[nei] == 0: |
| 26 | q.append(nei) |
| 27 | |
| 28 | return max(dp) |
Step-by-Step Solution
Build Graph and Indegree Array to Represent Prerequisites
| 3 | graph = defaultdict(list) |
| 4 | indegree = [0] * (n + 1) |
| 6 | for u, v in relations: |
| 7 | graph[u].append(v) |
| 8 | indegree[v] += 1 |
Objective
To represent course dependencies as a graph and track the number of prerequisites for each course.
Key Insight
Representing the problem as a graph with adjacency lists allows efficient traversal of dependent courses. The indegree array counts how many prerequisites each course has, enabling identification of courses ready to be taken (indegree zero). This setup is essential for topological sorting.
Interview Quick-Check
Core Logic
The graph adjacency list stores edges from each course to its dependent courses, and the indegree array tracks how many prerequisites remain before a course can be taken.
State & Boundaries
Courses with indegree zero have no prerequisites and can be started immediately.
Common Pitfalls & Bugs
Forgetting to increment indegree for the dependent course or misrepresenting edges can break the topological order.
Initialize Queue with Courses Having No Prerequisites and Set Their Completion Times
| 10 | q = deque() |
| 11 | dp = [0] * (n + 1) |
| 13 | for i in range(1, n + 1): |
| 14 | if indegree[i] == 0: |
| 15 | q.append(i) |
| 16 | dp[i] = time[i - 1] |
Objective
To identify starting courses and initialize their completion times based on their durations.
Key Insight
Courses without prerequisites can be taken immediately, so their earliest completion time is simply their own duration. Initializing the queue with these courses sets the stage for processing dependent courses in order.
Interview Quick-Check
Core Logic
Enqueueing courses with zero indegree ensures the BFS processes courses only when all prerequisites are met.
State & Boundaries
Setting dp[i] = time[i - 1] for zero indegree courses initializes their completion times correctly.
Common Pitfalls & Bugs
Failing to initialize dp for starting courses leads to incorrect propagation of completion times.
Process Courses in Topological Order to Compute Earliest Completion Times
| 18 | while q: |
| 19 | course = q.popleft() |
| 21 | for nei in graph[course]: |
| 22 | dp[nei] = max(dp[nei], dp[course] + time[nei - 1]) |
| 23 | indegree[nei] -= 1 |
| 25 | if indegree[nei] == 0: |
| 26 | q.append(nei) |
Objective
To iteratively update the earliest completion times of dependent courses by traversing the graph in topological order.
Key Insight
By processing courses whose prerequisites are completed, the algorithm updates the completion time of each dependent course to the maximum of its current value and the completion time of the prerequisite plus its own duration. This dynamic programming approach over the DAG ensures the earliest possible completion times are computed efficiently.
Interview Quick-Check
Core Logic
Updating dp[neighbor] with max(dp[neighbor], dp[current] + time[neighbor - 1]) propagates the longest prerequisite chain completion time.
State & Boundaries
Decrementing indegree and enqueueing neighbors when indegree reaches zero ensures correct topological order.
Common Pitfalls & Bugs
Not using max when updating dp can underestimate completion times, and failing to enqueue neighbors at zero indegree breaks the traversal.
Return the Maximum Completion Time Among All Courses
| 28 | return max(dp) |
Objective
To determine the total minimum time required to complete all courses by finding the longest completion time.
Key Insight
The overall completion time is dictated by the course with the longest prerequisite chain and duration. Taking the maximum value in dp captures this critical path length, which is the minimal total time to finish all courses.
Interview Quick-Check
Core Logic
The maximum value in dp represents the earliest time by which all courses can be completed.
Line Analysis
This solution has 5 Critical lines interviewers watch for.
dp[nei] = max(dp[nei], dp[course] + time[nei - 1])Update the earliest completion time for the dependent course.
This line embodies the core DP logic: the earliest completion time for a course is the maximum of its current value and the completion time of a prerequisite plus its own duration, ensuring all dependencies are respected.
indegree[v] += 1Increment the indegree count for course v.
Each prerequisite increases the indegree of the dependent course, tracking how many prerequisites remain before it can be taken.
dp[i] = time[i - 1]Set the completion time for courses without prerequisites to their own duration.
These courses can be completed in their own time since they have no dependencies, establishing base cases for dp.
if indegree[nei] == 0:If the dependent course has no remaining prerequisites, enqueue it.
Enqueuing courses only when all prerequisites are completed maintains correct topological order.
return max(dp)Return the maximum completion time among all courses.
The total minimum time to complete all courses is the longest time among all prerequisite chains, captured by the maximum dp value.
indegree = [0] * (n + 1)Create an indegree array to count prerequisites for each course.
Indegree tracking is essential for identifying courses without prerequisites, enabling topological sorting.
graph[u].append(v)Add v as a neighbor of u in the graph.
This edge represents that course v depends on course u, establishing the direction of prerequisite dependency.
dp = [0] * (n + 1)Create a dp array to store earliest completion times for each course.
This array tracks the minimal time to complete each course, enabling dynamic programming over the DAG.
if indegree[i] == 0:Check if the current course has zero prerequisites.
Courses with zero indegree can be started immediately, forming the BFS starting points.
while q:Process courses in the queue until empty.
This loop performs a BFS traversal in topological order, ensuring prerequisites are processed before dependent courses.
course = q.popleft()Dequeue the next course to process.
Processing courses in FIFO order respects dependency constraints and ensures correct dp updates.
indegree[nei] -= 1Decrement the indegree of the dependent course.
Reducing indegree tracks how many prerequisites remain before the course can be taken.
graph = defaultdict(list)Initialize the graph as a default dictionary of lists to store adjacency.
Using a defaultdict(list) allows efficient appending of edges without explicit initialization, simplifying graph construction.
q = deque()Initialize a queue to hold courses ready to be taken.
The queue supports BFS traversal of the graph in topological order, starting with courses having no prerequisites.
q.append(i)Add the course with zero indegree to the queue.
Enqueuing these courses initiates the topological traversal of the graph.
for nei in graph[course]:Iterate over all courses dependent on the current course.
Updating dependent courses propagates completion times through the graph, reflecting prerequisite chains.
q.append(nei)Add the dependent course to the queue for processing.
This schedules the course for completion time updates and further propagation.
for u, v in relations:Iterate over each prerequisite relation (u, v).
Processing each relation builds the graph and updates prerequisite counts, forming the problem's dependency structure.
for i in range(1, n + 1):Iterate over all courses from 1 to n.
This loop identifies courses without prerequisites to initialize the BFS traversal.
Test Your Understanding
Why does updating dp[neighbor] with max(dp[neighbor], dp[current] + time[neighbor - 1]) correctly compute the earliest completion time for each course?
Because a course can only start after all its prerequisites are completed, its earliest completion time is the maximum completion time among all its prerequisites plus its own duration. Taking the max ensures that the longest prerequisite chain is accounted for.
Related Problems
Graphs pattern
Don't just read it. Drill it.
Reconstruct Parallel Courses III from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Parallel Courses III drill