hard

Parallel Courses III

Find the minimum months to finish every course when courses can run in parallel.

1. Define the problem

Parallel Courses III

There are n courses labeled 1 to n, a list of prerequisite pairs relationsi = [prev, next], and timei giving the months course i + 1 takes. You may take any number of courses at the same time, as long as every prerequisite for a course has already been completed. Return the minimum number of months needed to complete every course. Process courses in topological order, tracking each course's finish time as its own duration plus the latest finish time among its prerequisites .

Constraints

  • 1 ≤ n ≤ 5 × 104
  • 0 ≤ relations.length ≤ min(n * (n - 1) / 2, 5 × 104)
  • time.length == n
  • 1 ≤ timei ≤ 104
  • The graph of prerequisites forms a DAG

Example

Inputn = 3, relations = [[1,3],[2,3]], time = [3,2,5]
Output8

Explanation Courses 1 and 2 run in parallel, finishing at months 3 and 2. Course 3 needs both done, so it starts at month 3 and finishes at month 3 + 5 = 8.

2. Know the words first

In plain terms

Finish time
How many months into the whole plan a course is done — its own duration added to whichever of its prerequisites finishes last.
3. Visualize the solution

Process in topological order, tracking the longest finish time so far

Process in topological order, tracking the longest finish time so far
Statusinit

Courses 1 and 2 have no prerequisites — their finish times start at their own durations, 3 and 2.

What happens in this step

in-degree[1] = 0, in-degree[2] = 0, in-degree[3] = 2

finish[1] = time[0] = 3
finish[2] = time[1] = 2
finish[3] = 0  (not yet reachable)

queue = [1, 2]

Courses 1 and 2 have no prerequisites, so each one's finish time is simply its own duration, and both start the queue.
Step 1 of 4

Steps to visualize

  1. Give every course with no prerequisites a finish time equal to its own duration, and queue it up.
  2. Pop a course from the queue; its finish time is now locked in.
  3. For each course it unlocks, update that course's candidate finish time to the larger of what it already had and this course's finish time plus its own duration.
  4. Once a course has heard from every prerequisite, its finish time is final and it joins the queue.
  5. The answer is the largest finish time seen across every course — the length of the longest dependency chain.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Process in topological order, tracking the longest finish time so far
Statusinit

Courses 1 and 2 have no prerequisites — their finish times start at their own durations, 3 and 2.

What happens in this step

in-degree[1] = 0, in-degree[2] = 0, in-degree[3] = 2

finish[1] = time[0] = 3
finish[2] = time[1] = 2
finish[3] = 0  (not yet reachable)

queue = [1, 2]

Courses 1 and 2 have no prerequisites, so each one's finish time is simply its own duration, and both start the queue.
Step 1 of 4
5. Solution

Solution

solution.tsTypeScript
function minimumTime(n, relations, time) {
  const graph = Array.from({ length: n + 1 }, () => []);
  const inDegree = new Array(n + 1).fill(0);

  for (const [prev, next] of relations) {
    graph[prev].push(next);
    inDegree[next]++;
  }

  const finish = new Array(n + 1).fill(0);
  const queue = [];

  for (let course = 1; course <= n; course++) {
    if (inDegree[course] === 0) {
      finish[course] = time[course - 1];
      queue.push(course);
    }
  }

  let answer = 0;

  while (queue.length > 0) {
    const course = queue.shift();
    answer = Math.max(answer, finish[course]);

    for (const next of graph[course]) {
      finish[next] = Math.max(finish[next], finish[course] + time[next - 1]);
      inDegree[next]--;
      if (inDegree[next] === 0) {
        queue.push(next);
      }
    }
  }

  return answer;
}
Time
O(n + relations.length)
Space
O(n + relations.length)
6. Test cases

Test cases

InputExpectedCovers
n = 3, relations = [[1,3],[2,3]], time = [3,2,5]8example from the docstring, two parallel prerequisites feeding one course
n = 5, relations = [[1,5],[2,5],[3,5],[3,4],[4,5]], time = [1,2,3,4,5]12a course with several prerequisites, one of which has its own prerequisite
n = 1, relations = [], time = [7]7smallest valid input, a single course with no relations
n = 3, relations = [[1,2],[2,3]], time = [1,1,1]3a straight chain where every course waits on the one before it
n = 4, relations = [], time = [2,10,3,7]10no relations at all, so every course runs in parallel and the slowest one wins
n = 4, relations = [[1,2],[1,3],[2,4],[3,4]], time = [1,2,3,10]14two branches of different length converging on one final course
n = 2, relations = [[1,2]], time = [100,1]101a long first course followed by a short one still sums along the chain
n = 6, relations = [[1,2],[2,3],[4,5],[5,6]], time = [1,1,1,10,10,10]30two unrelated chains of the same length but very different durations run in parallel

Keep reading