Parallel Courses

Parallel Courses medium

Description

You are given an integer n, which indicates that there are n courses labeled from 1 to n. You are also given an array relations where relations[i] = [prevCourse_i, nextCourse_i], representing a prerequisite relationship between courses prevCourse_i and nextCourse_i: course prevCourse_i has to be taken before course nextCourse_i.

In one semester, you can take any number of courses as long as you have taken all the prerequisites in the previous semester for the courses you are taking.

Return the minimum number of semesters needed to take all courses. If there is no way to take all the courses, return -1.

Examples

> Case 1:
    n = 3,  relations = [[1, 3], [2, 3]]
    Output: 2
    Explanation: semester 1: take courses 1 and 2 in parallel; semester 2: take course 3.
 
> Case 2:
    n = 3,  relations = [[1, 2], [2, 3], [3, 1]]
    Output: -1
    Explanation: cyclic — impossible.

Constraints

1 <= n <= 5000
1 <= relations.length <= 5000
relations[i].length == 2

State design

This is the Kahn’s-with-rounds variation from the Kahn’s page.

Round 0: every course with no prerequisites.
Round k: every course whose prerequisites were all completed by round k - 1.

The total number of rounds is the minimum number of semesters — equivalent to the length of the longest path in the DAG.

If a cycle exists, some courses are never processed → return -1.

Code

Why does this equal the longest path? Each “round” processes one level of the DAG. Nodes are placed at level k iff their longest predecessor chain has length k. The total number of rounds = max level + 1 = (longest chain in the DAG). That’s the answer.

Variation — DP-based longest path

You can also compute the answer as a longest-path DP on the DAG:

def minimum_semesters_dp(n, relations):
    adj = [[] for _ in range(n + 1)]
    indeg = [0] * (n + 1)
    for u, v in relations:
        adj[u].append(v); indeg[v] += 1
    # Topo sort
    from collections import deque
    q = deque(i for i in range(1, n + 1) if indeg[i] == 0)
    topo = []
    while q:
        u = q.popleft(); topo.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0: q.append(v)
    if len(topo) < n: return -1
    dp = [1] * (n + 1)              # longest path ending at u, including u
    for u in topo:
        for v in adj[u]:
            dp[v] = max(dp[v], dp[u] + 1)
    return max(dp[1:])

Same O(V + E) — different framing, same answer. The longest-path-on-DAG technique is a useful tool to have on its own.

Analysis

Time: O(V + E).
Space: O(V + E).

Same skin

Parallel Courses II — same problem with the constraint “at most k courses per semester.” NP-hard in general; the LeetCode version uses bitmask DP.
Parallel Courses III — courses have durations; minimize total time (DAG longest weighted path).
Longest Increasing Path in a Matrix — DAG longest path applied to grid cells.
Course Schedule III — different problem entirely (sorting + greedy).

Minimum Height Trees Alien Dictionary