Quick Overview

Given up to fifteen courses with prerequisites and a cap of k courses per semester, return the fewest semesters needed to take every course. It tests why simple greedy choices fail and how to search the space of partial plans efficiently.

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

Company: Snowflake

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

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 ```python 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** ```text 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** ```text 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** ```text 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.

Overview: Given up to fifteen courses with prerequisites and a cap of k courses per semester, return the fewest semesters needed to take every course. It tests why simple greedy choices fail and how to search the space of partial plans efficiently.

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. Implement `min_semesters(n, prerequisites, k)`. ### 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. ### Output Return one integer: the minimum number of semesters. It is always between `1` and `n`. No input value or result can exceed 2^31 - 1, so 32-bit integers suffice in every language. ### 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. ### Example 1 ```text 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 ```text 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.

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

Input: (4, [[0, 1], [0, 2], [3, 0]], 2)

Expected Output: 3

Explanation: Source Example 1: courses 1 and 2, then 0, then 3; the chain 1, 0, 3 needs three semesters.

Input: (5, [[1, 0], [2, 1]], 2)

Expected Output: 3

Explanation: Source Example 2: take 0 and 3, then 1 and 4, then 2. Starting with the free courses 3 and 4 costs a fourth semester, and summing ceil(level size / k) over depth levels also gives 4.

Hints

  1. Example 2 shows that which ready courses you take in a semester matters: a choice that looks harmless now can leave a long prerequisite chain unfinished and add a semester at the end.
  2. The longest prerequisite chain and ceil(n / k) are both lower bounds on the answer, but they are not always tight: several prerequisites that all feed one course can force an extra semester.
  3. With n at most 15, it is affordable to reason about exactly which courses are already finished, not just how many.

Loading coding console...

Show the approach

Approach

Encode the set of finished courses as an n-bit mask and precompute, for each course, the mask of its prerequisites (pair [course, before] sets bit before in need[course]). From a finished set S, a course is ready when it is not in S and need[course] is a subset of S. Breadth-first search runs over finished sets starting from the empty set: each BFS level is one semester, and the answer is the level at which the full mask first appears.

Pruning that keeps the search small: from S with r ready courses it suffices to take exactly min(k, r) of them. Finishing more never hurts: if S is a subset of S' (both closed under prerequisites), any schedule from S can be replayed from S' by dropping courses already finished, without adding semesters. So any smaller group of ready courses can be extended to min(k, r) ready courses without increasing the remaining semesters. When r <= k the only move takes every ready course; otherwise the search tries every k-subset of the ready courses. A seen array expands each finished set once, so the first level that reaches the full set is the minimum.

Invariant: level t holds exactly the finished sets first reachable after t semesters under the pruned moves, and the pruned moves preserve the optimum.

Edge cases: n = 1 gives 1; no prerequisites gives ceil(n / k); with k = n the longest chain decides. Because the prerequisites are acyclic, every unfinished set has a ready course, so the search always progresses. Greedy rules (lowest index first, most dependents first, free courses first) and formulas such as max(longest chain, ceil(n / k)) or the sum of ceil(level size / k) over depth levels all fail on some inputs: Example 2 defeats the free-courses-first rule and the level sum, and course 0 needing courses 1, 2 and 3 and preceding course 4 with k = 2 needs 4 semesters while max(longest chain, ceil(n / k)) gives 3.

Time complexity:
O(3^n + n * 2^n)
Space complexity:
O(2^n)