Parallel Courses

Problem (restated)

n courses (1..n) with prerequisites [prev, next]. You may take any number of courses with satisfied prereqs each semester. Min semesters to finish all, or -1 if impossible.

Intuition

Layered Kahn: each BFS layer is one semester. If not all courses taken, cycle → -1.

Approaches

export function minimumSemesters(n: number, relations: number[][]): number {
  const g: number[][] = Array.from({ length: n + 1 }, () => []);
  const indeg = Array(n + 1).fill(0);
  for (const e of relations) {
    g[e[0]!]!.push(e[1]!);
    indeg[e[1]!]!++;
  }
  let q: number[] = [];
  for (let i = 1; i <= n; i++) if (indeg[i] === 0) q.push(i);
  let sem = 0, taken = 0;
  while (q.length) {
    const next: number[] = [];
    for (const u of q) {
      taken++;
      for (const v of g[u]!) {
        if (--indeg[v]! === 0) next.push(v);
      }
    }
    sem++;
    q = next;
  }
  return taken === n ? sem : -1;
}

export function minimumSemesters(n: number, relations: number[][]): number {
  const g: number[][] = Array.from({ length: n + 1 }, () => []);
  const indeg = Array(n + 1).fill(0);
  for (const e of relations) {
    g[e[0]!]!.push(e[1]!);
    indeg[e[1]!]!++;
  }
  let q: number[] = [];
  for (let i = 1; i <= n; i++) if (indeg[i] === 0) q.push(i);
  let sem = 0, taken = 0;
  while (q.length) {
    const next: number[] = [];
    for (const u of q) {
      taken++;
      for (const v of g[u]!) {
        if (--indeg[v]! === 0) next.push(v);
      }
    }
    sem++;
    q = next;
  }
  return taken === n ? sem : -1;
}

Template connection

Topological sort with level counting.

Reflection

• One Kahn layer is one semester. Every indegree-0 course in that round runs together. The answer is the number of layers.
• A cycle drains the queue before every course is taken: answer −1. No edges means every course fits in semester 1.
• A chain of n courses takes n semesters. Two courses with no edge take one semester.