Fewest Semesters to Finish All Courses Taking At Most k per Semester

Courses are numbered 0 to n - 1, and some courses must be completed before others. You take courses in semesters: in each semester you may take at most k courses, and a course can be taken only after all of its prerequisites were completed in earlier semesters. Return the minimum number of semesters needed to take every course.

Function Signature

def min_semesters(n: int, prerequisites: list[list[int]], k: int) -> int:

Rules

• Each pair [course, before] in prerequisites means that course before must be completed in an earlier semester than course course.
• In one semester you may take any set of at most k courses whose prerequisites were all completed in earlier semesters. Courses taken in the same semester cannot satisfy each other's prerequisites.
• Each course is taken exactly once and is completed at the end of the semester in which it is taken.
• The prerequisites contain no cycle, so every course can be taken.

Constraints

• 1 <= n <= 15
• 1 <= k <= n
• 0 <= len(prerequisites) <= n * (n - 1) / 2
• Each pair holds two different course numbers between 0 and n - 1, no pair appears twice, and the pairs contain no cycle.

Examples

Example 1

Input: n = 4, prerequisites = [[0, 1], [0, 2], [3, 0]], k = 2
Output: 3

Take courses 1 and 2 in the first semester, course 0 in the second and course 3 in the third. The chain 1, 0, 3 rules out fewer than three semesters.

Example 2

Input: n = 5, prerequisites = [[1, 0], [2, 1]], k = 2
Output: 3

Take courses 0 and 3, then 1 and 4, then 2. Starting with courses 3 and 4 instead would leave the chain 0, 1, 2 needing three more semesters, four in total.

Example 3

Input: n = 5, prerequisites = [[0, 1], [0, 2], [0, 3], [4, 0]], k = 2
Output: 4

Courses 1, 2 and 3 need two semesters at two courses per semester. Course 0 follows in the third semester and course 4 in the fourth.