NeetCode #624LC-2050HardGraphs
← Back to All Problems#624 · #2050 · Parallel Courses III(并行课程 III)
📌 Problem Statement & Constraints
You are given
n courses, relations[i] = [a, b] meaning a must be taken before b, and time[i] for the duration of course i+1. Courses with satisfied prerequisites run in parallel. Return the minimum time to complete all courses. Constraints: 1 <= n <= 5 * 10^4, 0 <= relations.length <= min(n*(n-1)/2, 5*10^4), 1 <= time[i] <= 10^4.💡 Core Algorithmic Approaches
- Topological sort with a longest-path DP:
finish[i]is the earliest time courseicompletes. - When a node is popped, all its prerequisites are done, so
finish[i] += time[i]. - Propagate
max(finish[nxt], finish[node])to each successor -- the successor can only start after the latest prerequisite. - The answer is the maximum finish time over all courses.
💻 Benchmark Python3 Implementation
class Solution:
def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:
from collections import defaultdict, deque
g = defaultdict(list)
indeg = [0] * (n + 1) # courses are 1-indexed
for a, b in relations:
g[a].append(b)
indeg[b] += 1
finish = [0] * (n + 1)
q = deque(i for i in range(1, n + 1) if indeg[i] == 0)
while q:
node = q.popleft()
finish[node] += time[node - 1] # all prerequisites are done
for nxt in g[node]:
if finish[node] > finish[nxt]:
finish[nxt] = finish[node] # the latest prerequisite wins
indeg[nxt] -= 1
if indeg[nxt] == 0:
q.append(nxt)
return max(finish)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(V + E): each node and edge is processed once.
💾 Space Complexity
O(V + E) for the graph and the finish array.
⚠️ Interview Pitfalls & Follow-ups
- Summing all durations: parallel courses overlap, so the answer is a longest path.
- Propagating the successor's own duration: only the prerequisite's finish time propagates.
- Adding the duration when the node is enqueued: the finish time is only final once the in-degree reaches 0.
- Using
sum(time)for a chain: the longest path is what matters.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.