Parallel Courses III
Asked at Snowflake
Problem
Parallel Courses III gives you courses with durations and prerequisite relations, and lets you take any number of courses at the same time. What is the minimum time to finish them all? It is the longest (critical) path through a DAG, computed with a topological sort.
Asked At
| Company | Difficulty | |
|---|---|---|
| Snowflake | Hard | View all Snowflake questions → |
How to Think About It
Because courses can run in parallel, a course starts as soon as its last prerequisite finishes. The overall finish time is the latest finish of any course.
Key insight: finish[v] = time[v] + max(finish[u] for each prerequisite u). That is DP over a DAG in topological order — the critical-path method from project scheduling.
Kahn's algorithm: start with all courses that have no prerequisites (finish = time). When you pop u, update each dependent v with start[v] = max(start[v], finish[u]) and decrement its in-degree; enqueue it at zero.
The answer is max(finish).
Walkthrough: n = 3, relations 1->3, 2->3, times [3,2,5]: course 3 starts at max(3, 2) = 3 and finishes at 8.
Optimal Approach
Step 1: Build adjacency lists and in-degrees (courses are 1-indexed).
Step 2: start = [0] * n; enqueue courses with in-degree 0.
Step 3: Pop u: finish = start[u] + time[u]; for each v in adj[u]: start[v] = max(start[v], finish); decrement in-degree; enqueue at 0.
Step 4: Return max(start[i] + time[i]).
Time: O(n + e). Space: O(n + e).
What Trips People Up in Real Interviews
Summing all durations. Courses run in parallel, so only the critical path matters.
Using BFS levels (like Parallel Courses I) and adding one duration per level — levels ignore that courses in the same level have different durations.
Off-by-one on 1-indexed course numbers.
Returning the finish time of the last course dequeued rather than the maximum over all courses.
Solution Code
from collections import deque
def minimumTime(n, relations, time):
adj = [[] for _ in range(n)]
indeg = [0] * n
for a, b in relations:
adj[a - 1].append(b - 1)
indeg[b - 1] += 1
start = [0] * n
q = deque(i for i in range(n) if indeg[i] == 0)
while q:
u = q.popleft()
done = start[u] + time[u]
for v in adj[u]:
start[v] = max(start[v], done)
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
return max(start[i] + time[i] for i in range(n))Frequently Asked Questions
What is the Parallel Courses III problem?
Parallel Courses III gives you courses with durations and prerequisite relations, and lets you take any number of courses at the same time. What is the minimum time to finish them all? It is the longest (critical) path through a DAG, computed with a topological sort.
How do you solve Parallel Courses III?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Parallel Courses III?
Parallel Courses III is asked at Snowflake. It is a hard difficulty problem.
What are common mistakes on Parallel Courses III?
- Summing all durations. Courses run in parallel, so only the critical path matters.
- Using BFS levels (like Parallel Courses I) and adding one duration per level — levels ignore that courses in the same level have different durations.
- Off-by-one on 1-indexed course numbers.
- Returning the finish time of the last course dequeued rather than the maximum over all courses.