Parallel Courses
Medium · Graphs · Graph · Topological Sort
Problem
There are n courses labeled 1 to n. Each relations[i] = [prev, next] means course prev has to be completed before course next can be taken.
In one semester you may take any number of courses, as long as every prerequisite of each of them was finished in an earlier semester. Return the minimum number of semesters needed to take all courses, or -1 if it cannot be done because the prerequisites form a cycle.
Examples
Input: n = 4, relations = [[1,3],[2,3],[3,4]] Output: 3
Semester 1: courses 1 and 2. Semester 2: course 3. Semester 3: course 4.
Input: n = 3, relations = [[1,2],[2,3],[3,1]] Output: -1
The prerequisites loop, so none of the three courses can ever be started.
Input: n = 3, relations = [[1,2]] Output: 2
Courses 1 and 3 go in the first semester and course 2 in the second.
Constraints
- 1 <= n <= 5000
- 1 <= len(relations) <= 5000
- relations[i] == [prev, next] with 1 <= prev, next <= n and prev != next
- All pairs are distinct
Approaches
- Baseline: raise semesters until nothing changes — time O(n · m), space O(n)
Follow-up
With a cap of k courses per semester the problem becomes hard: choosing which available courses to take first matters, and the known solutions are exponential (bitmask DP for small n). The use cases keep unlimited parallelism and give each course its own duration, and ask for the semester of every course instead of the count.
Related problems
Start free on Cariara · Coding problems · System design studio
