Stage 5: Interview Simulation·Timed Random Hards

Hard#20509 min readTopological SortDPDAGSchedulingLeetCode

Parallel Courses III

Kahn's topological sort with longest-path DP

Topo sort + DP for critical path. Think scheduling.

Published Apr 17, 2026

Problem

You have n courses labeled 1..=n. Each course i takes time[i] months. Some courses have prerequisite relations relations[k] = [u, v] meaning u must finish before v can start. You can take any number of courses in parallel as long as every prerequisite is done.

Return the minimum number of months to finish all courses.

Input

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

Output

Explanation

Courses 1 and 2 run in parallel (done at month 3). Course 3 starts at month 3 and finishes at month 8.

Input

n = 5, relations = [[1,5],[2,5],[3,5],[3,4],[4,5]], time = [1,2,3,4,5]

Output

Explanation

Critical path is 3 → 4 → 5 with total 3 + 4 + 5 = 12. Other paths into 5 finish earlier and don't dominate.

Intuition

This is the classical critical path problem on a DAG. The minimum schedule length is the longest weighted path from any source (no prerequisites) to any sink (no successors), where each node's weight is its duration.

Longest-path on a DAG is computed in O(n + m) by processing nodes in topological order and relaxing: dp[v] = time[v] + max(dp[u] for u → v). With no prerequisites, dp[v] = time[v] and that's the base case.

Kahn's algorithm gives the topological order "for free" as it drains a zero-indegree queue. Alternatively, a DFS with memoization computes dp[v] lazily; both approaches cost the same asymptotically.

Approach

DFS with memoization

TimeO(n + m)

SpaceO(n + m)

Build reverse adjacency (predecessors). Define dp(v) = time[v] + max(dp(u) for u prereq of v, default 0). Return max(dp(v) for v).

Because the graph is a DAG, the recursion terminates; memoization ensures every node is visited once. Stack depth can be O(n) on adversarial chains — iterative Kahn avoids that risk.

impl Solution {
    pub fn minimum_time(n: i32, relations: Vec<Vec<i32>>, time: Vec<i32>) -> i32 {
        let n = n as usize;
        let mut prereq = vec![Vec::<usize>::new(); n];
        for r in &relations {
            prereq[(r[1] - 1) as usize].push((r[0] - 1) as usize);
        }
        let mut memo = vec![-1i32; n];
        fn dfs(v: usize, prereq: &[Vec<usize>], time: &[i32], memo: &mut [i32]) -> i32 {
            if memo[v] >= 0 { return memo[v]; }
            let mut best = 0;
            for &u in &prereq[v] { best = best.max(dfs(u, prereq, time, memo)); }
            memo[v] = best + time[v];
            memo[v]
        }
        (0..n).map(|v| dfs(v, &prereq, &time, &mut memo)).max().unwrap_or(0)
    }
}

Rust · runnable

function minimumTime(n: number, relations: number[][], time: number[]): number {
  const prereq: number[][] = Array.from({ length: n }, () => []);
  for (const [u, v] of relations) prereq[v - 1].push(u - 1);
  const memo = new Array(n).fill(-1);
  const dfs = (v: number): number => {
    if (memo[v] >= 0) return memo[v];
    let best = 0;
    for (const u of prereq[v]) best = Math.max(best, dfs(u));
    memo[v] = best + time[v];
    return memo[v];
  };
  let ans = 0;
  for (let v = 0; v < n; v++) ans = Math.max(ans, dfs(v));
  return ans;
}

TypeScript · runnable

Kahn's Topological Sort + DP

TimeO(n + m)

SpaceO(n + m)

Recommended

Build forward adjacency and indegrees.
Seed dp[v] = time[v] for every source (indeg[v] == 0) and push them into a queue.
Pop u; for each edge u → v: dp[v] = max(dp[v], dp[u] + time[v]); decrement indeg[v]; when indeg[v] hits 0, push v.
Answer is max(dp).

The neat invariant: when v pops off the queue, every predecessor has already been processed, so dp[v] is final.

use std::collections::VecDeque;

impl Solution {
    pub fn minimum_time(n: i32, relations: Vec<Vec<i32>>, time: Vec<i32>) -> i32 {
        let n = n as usize;
        let mut adj = vec![Vec::<usize>::new(); n];
        let mut indeg = vec![0i32; n];
        for r in &relations {
            let (u, v) = ((r[0] - 1) as usize, (r[1] - 1) as usize);
            adj[u].push(v);
            indeg[v] += 1;
        }

        let mut dp = vec![0i32; n];
        let mut q: VecDeque<usize> = VecDeque::new();
        for v in 0..n {
            if indeg[v] == 0 {
                dp[v] = time[v];
                q.push_back(v);
            }
        }

        while let Some(u) = q.pop_front() {
            for &v in &adj[u] {
                if dp[u] + time[v] > dp[v] { dp[v] = dp[u] + time[v]; }
                indeg[v] -= 1;
                if indeg[v] == 0 { q.push_back(v); }
            }
        }

        *dp.iter().max().unwrap_or(&0)
    }
}

Rust · runnable

function minimumTime(n: number, relations: number[][], time: number[]): number {
  const adj: number[][] = Array.from({ length: n }, () => []);
  const indeg = new Array(n).fill(0);
  for (const [u, v] of relations) { adj[u - 1].push(v - 1); indeg[v - 1]++; }

  const dp = new Array(n).fill(0);
  const queue: number[] = [];
  for (let v = 0; v < n; v++) if (indeg[v] === 0) { dp[v] = time[v]; queue.push(v); }

  let head = 0;
  while (head < queue.length) {
    const u = queue[head++];
    for (const v of adj[u]) {
      if (dp[u] + time[v] > dp[v]) dp[v] = dp[u] + time[v];
      indeg[v]--;
      if (indeg[v] === 0) queue.push(v);
    }
  }

  let ans = 0;
  for (const d of dp) if (d > ans) ans = d;
  return ans;
}

TypeScript · runnable

Trace

On example 2 (n=5, relations [[1,5],[2,5],[3,5],[3,4],[4,5]], times [1,2,3,4,5]):

step	queue	processed	dp after
init	[1, 2, 3]	—	[1, 2, 3, 0, 0]
pop 1	[2, 3]	relax 5 → dp[5]=6	[1, 2, 3, 0, 6]
pop 2	[3]	relax 5 → dp[5]=7	[1, 2, 3, 0, 7]
pop 3	[4, 5]	relax 4 → dp[4]=7; relax 5 → dp[5]=8	[1, 2, 3, 7, 8]
pop 4	[5]	relax 5 → dp[5]=12	[1, 2, 3, 7, 12]
pop 5	[]	—	[1, 2, 3, 7, 12]

Answer = max(dp) = 12.

Edge cases

No prerequisites — every course is a source; answer is max(time) (all run in parallel).
Single chain — answer is sum(time) along the chain; parallelism adds nothing.
Disconnected components — Kahn's processes them independently; final max(dp) picks whichever component's critical path is longest.
Non-positive times — not in the LC constraints (1 ≤ time[i]), but the recurrence still works for non-negative integers.

Takeaway

Longest path on a DAG → topological sort + linear DP. Any "earliest finish time under precedence constraints" question — course schedules, build graphs, CI pipelines, asynchronous task DAGs — reduces to this recurrence. Production relevance: this is exactly how Bazel / Nx estimate build times, and how Airflow computes the critical path of a DAG run.

In the 30-minute interview frame: spot the precedence hint, declare Kahn + DP, code it in one pass. The trap is forgetting to initialize dp[v] = time[v] at the sources, which produces an off-by-one of exactly one "first task duration" short.

Medium#207

Course Schedule

Cycle detection in directed graph. Both DFS (3-color) and Kahn’s BFS work.

Medium#210

Course Schedule II

Topological sort — output the ordering, not just detect cycles.

Medium#787

Cheapest Flights Within K Stops

Bellman-Ford with K rounds. You already know this from your arb bot.