194. Minimum Semesters

Why this mechanism works

Kahn's available frontier forms one semester. Capture its width so dependents released during processing wait until the next semester. Delaying an already available course cannot help under unlimited parallel capacity, so taking the entire frontier is optimal.

State and boundaries

The queue at each outer-loop start contains exactly courses whose prerequisites finished in earlier semesters. semesters counts fully scheduled layers.

Protocol

1. Build prerequisite edges and indegrees.
2. Queue all initially available courses.
3. Increment semesters once per captured layer.
4. Process only that layer and release next-semester courses.
5. Return semesters if every course was processed, otherwise -1.

Visualization

0 -> 2
1 -> 2 -> 3
semester 1: [0,1]
semester 2: [2]
semester 3: [3]

Python implementation

from collections import deque

def min_semesters(n, prerequisites):
    adj, indegree = [[] for _ in range(n)], [0] * n
    for course, prerequisite in prerequisites:
        adj[prerequisite].append(course)
        indegree[course] += 1
    queue = deque(u for u in range(n) if indegree[u] == 0)
    semesters = processed = 0
    while queue:
        semesters += 1
        width = len(queue)
        for _ in range(width):
            u = queue.popleft()
            processed += 1
            for v in adj[u]:
                indegree[v] -= 1
                if indegree[v] == 0:
                    queue.append(v)
    return semesters if processed == n else -1

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L4 min_semesters: adj, indegree = [[] for _ in range(n)], [0] * n
n=4; prerequisites=[(2, 0), (2, 1), (3, 2)]; _=0

L4 min_semesters: adj, indegree = [[] for _ in range(n)], [0] * n
n=4; prerequisites=[(2, 0), (2, 1), (3, 2)]; _=1

L4 min_semesters: adj, indegree = [[] for _ in range(n)], [0] * n
n=4; prerequisites=[(2, 0), (2, 1), (3, 2)]; _=2

L4 min_semesters: adj, indegree = [[] for _ in range(n)], [0] * n
n=4; prerequisites=[(2, 0), (2, 1), (3, 2)]; _=3

L4 min_semesters: adj, indegree = [[] for _ in range(n)], [0] * n
n=4; prerequisites=[(2, 0), (2, 1), (3, 2)]; adj=[[], [], [], []]; indegree=[0, 0, 0, 0]

L5 min_semesters: for course, prerequisite in prerequisites:
n=4; prerequisites=[(2, 0), (2, 1), (3, 2)]; adj=[[], [], [], []]; indegree=[0, 0, 0, 0]; course=2; prerequisite=0

L6 min_semesters: adj[prerequisite].append(course)
n=4; prerequisites=[(2, 0), (2, 1), (3, 2)]; adj=[[2], [], [], []]; indegree=[0, 0, 0, 0]; course=2; prerequisite=0

L7 min_semesters: indegree[course] += 1
n=4; prerequisites=[(2, 0), (2, 1), (3, 2)]; adj=[[2], [], [], []]; indegree=[0, 0, 1, 0]; course=2; prerequisite=0

... 31 intermediate state changes omitted ...

L19 min_semesters: queue.append(v)
n=4; prerequisites=[(2, 0), (2, 1), (3, 2)]; adj=[[2], [2], [3], []]; indegree=[0, 0, 0, 0]; course=3; prerequisite=2; queue=deque([3]); semesters=2; processed=3; width=1; _=0; u=2; v=3

L11 min_semesters: semesters += 1
n=4; prerequisites=[(2, 0), (2, 1), (3, 2)]; adj=[[2], [2], [3], []]; indegree=[0, 0, 0, 0]; course=3; prerequisite=2; queue=deque([3]); semesters=3; processed=3; width=1; _=0; u=2; v=3

L14 min_semesters: u = queue.popleft()
n=4; prerequisites=[(2, 0), (2, 1), (3, 2)]; adj=[[2], [2], [3], []]; indegree=[0, 0, 0, 0]; course=3; prerequisite=2; queue=deque([]); semesters=3; processed=3; width=1; _=0; u=3; v=3

L15 min_semesters: processed += 1
n=4; prerequisites=[(2, 0), (2, 1), (3, 2)]; adj=[[2], [2], [3], []]; indegree=[0, 0, 0, 0]; course=3; prerequisite=2; queue=deque([]); semesters=3; processed=4; width=1; _=0; u=3; v=3

L4 min_semesters: adj, indegree = [[] for _ in range(n)], [0] * n
n=2; prerequisites=[(1, 0), (0, 1)]; _=0

L4 min_semesters: adj, indegree = [[] for _ in range(n)], [0] * n
n=2; prerequisites=[(1, 0), (0, 1)]; _=1

L4 min_semesters: adj, indegree = [[] for _ in range(n)], [0] * n
n=2; prerequisites=[(1, 0), (0, 1)]; adj=[[], []]; indegree=[0, 0]

L5 min_semesters: for course, prerequisite in prerequisites:
n=2; prerequisites=[(1, 0), (0, 1)]; adj=[[], []]; indegree=[0, 0]; course=1; prerequisite=0

L6 min_semesters: adj[prerequisite].append(course)
n=2; prerequisites=[(1, 0), (0, 1)]; adj=[[1], []]; indegree=[0, 0]; course=1; prerequisite=0

L7 min_semesters: indegree[course] += 1
n=2; prerequisites=[(1, 0), (0, 1)]; adj=[[1], []]; indegree=[0, 1]; course=1; prerequisite=0

L5 min_semesters: for course, prerequisite in prerequisites:
n=2; prerequisites=[(1, 0), (0, 1)]; adj=[[1], []]; indegree=[0, 1]; course=0; prerequisite=1

L6 min_semesters: adj[prerequisite].append(course)
n=2; prerequisites=[(1, 0), (0, 1)]; adj=[[1], [0]]; indegree=[0, 1]; course=0; prerequisite=1

... 1 intermediate state changes omitted ...

L8 <genexpr>: queue = deque(u for u in range(n) if indegree[u] == 0)
.0=range_iterator; u=0; indegree=[1, 1]

L8 <genexpr>: queue = deque(u for u in range(n) if indegree[u] == 0)
.0=range_iterator; u=1; indegree=[1, 1]

L8 min_semesters: queue = deque(u for u in range(n) if indegree[u] == 0)
n=2; prerequisites=[(1, 0), (0, 1)]; adj=[[1], [0]]; indegree=[1, 1]; course=0; prerequisite=1; queue=deque([])

L9 min_semesters: semesters = processed = 0
n=2; prerequisites=[(1, 0), (0, 1)]; adj=[[1], [0]]; indegree=[1, 1]; course=0; prerequisite=1; queue=deque([]); semesters=0; processed=0

Why the solution is correct

A course cannot finish before one semester after its latest prerequisite. The layer algorithm schedules it at exactly that earliest possible semester. Induction over layers proves all finish times minimal; the largest is the minimum total semesters. An unprocessed cycle makes completion impossible.

Time and space

O(n+m) time and space.

Common mistakes

Processing newly released courses in the current semester lets prerequisites and dependents finish together illegally. A per-semester capacity limit would require a different optimization problem.

Reasoning card

Transfer exercise

Return each course's earliest finishing semester and reconstruct a longest prerequisite chain.