How do you solve Parallel Courses III?

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.

What pattern does Parallel Courses III use?

The Pattern: Topological Sort (Dependency Resolution with DP) The Heuristic: 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.

Parallel Courses III — Topological Sort

Q: What is the time complexity of Parallel Courses III?

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.

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

Input: n = 3, relations = [[1,3],[2,3]], time = [3,2,5]

Output: 8

Courses 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

Preview

Recognizing the problem as a DAG with dependencies suggests using topological sort to process courses in order of prerequisites…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

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…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

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.

Solution

Python

1class Solution:
  def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:
      graph = defaultdict(list)
      indegree = [0] * (n + 1)
5
      for u, v in relations:
          graph[u].append(v)
          indegree[v] += 1
9
      q = deque()
      dp = [0] * (n + 1)
12
      for i in range(1, n + 1):
          if indegree[i] == 0:
              q.append(i)
              dp[i] = time[i - 1]
17
      while q:
          course = q.popleft()
20
          for nei in graph[course]:
              dp[nei] = max(dp[nei], dp[course] + time[nei - 1])
              indegree[nei] -= 1
24
              if indegree[nei] == 0:
                  q.append(nei)
27
      return max(dp)

Step-by-Step Solution

1

Build Graph and Indegree Array to Represent Prerequisites

3graph = defaultdict(list)
4indegree = [0] * (n + 1)
6for 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.

2

Initialize Queue with Courses Having No Prerequisites and Set Their Completion Times

To identify starting courses and initialize their completion times based on their durations.

3

Process Courses in Topological Order to Compute Earliest Completion Times

To iteratively update the earliest completion times of dependent courses by traversing the graph in topological order.

4

Return the Maximum Completion Time Among All Courses

To determine the total minimum time required to complete all courses by finding the longest completion time.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 5 Critical lines interviewers watch for.

Line 22 Critical

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.

Line 8 Critical

indegree[v] += 1

Increment 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.

Line 16 Critical

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.

Full line-by-line criticality + rationale for all 19 lines available on Pro.

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?

See the answer with Pro.

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

or drill a free problem

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)`

3	`graph = defaultdict(list)`
4	`indegree = [0] * (n + 1)`
6	`for u, v in relations:`
7	`graph[u].append(v)`
8	`indegree[v] += 1`