hardBit ManipulationPure DSA~55 min
Fewest Semesters With a Per-Term Course Cap
A degree has prerequisite dependencies between courses. Each semester you may take at most k courses, all of whose prerequisites were completed earlier. Find the fewest semesters to finish.
Problem
Given n courses labeled 1..n, a list of prerequisite pairs relations where [a, b] means a must be taken before b, and an integer k limiting courses per semester, return the minimum number of semesters to complete all courses. It is guaranteed the prerequisites form a DAG.
Input
Integers n and k, and a list of [prev, next] prerequisite pairs.
Output
An integer: the minimum number of semesters.
Constraints
- 1 <= n <= 15
- 1 <= k <= n
- relations form a valid DAG (no cycles).
Examples
Example 1
Input
n = 4, relations = [[2,1],[3,1],[1,4]], k = 2
Output
3
Semester 1: {2,3}; semester 2: {1}; semester 3: {4}.
Example 2
Input
n = 5, relations = [[2,1],[3,1],[4,1],[1,5]], k = 2
Output
4
Three prerequisites of 1 across two semesters, then 1, then 5.