⚡Flashcard Drill➔
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

  1. Topological sort with a longest-path DP: finish[i] is the earliest time course i completes.
  2. When a node is popped, all its prerequisites are done, so finish[i] += time[i].
  3. Propagate max(finish[nxt], finish[node]) to each successor -- the successor can only start after the latest prerequisite.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems