Capped Semester Planner

HardBit Manipulation

Problem

A student must pass courseCount courses numbered 0 to courseCount - 1. Each pair [before, after] in prerequisites means before must be passed in an earlier semester than after. The prerequisites never form a cycle.

In one semester the student can take at most perTerm courses, and only courses whose prerequisites were all passed in earlier semesters. Return the minimum number of semesters needed to pass every course.

Example 1

Input:
courseCount = 4, prerequisites = [[1, 0], [2, 0], [0, 3]], perTerm = 2
Output:
3

{1, 2}, then {0}, then {3}.

Example 2

Input:
courseCount = 5, prerequisites = [[0, 1], [1, 2]], perTerm = 2
Output:
3

{0, 3}, {1, 4}, {2}. Taking the free courses 3 and 4 first would cost four semesters.

Example 3

Input:
courseCount = 3, prerequisites = [], perTerm = 3
Output:
1

Constraints

  • 1 ≤ courseCount ≤ 13
  • 0 ≤ prerequisites.length ≤ courseCount · (courseCount - 1) / 2
  • 1 ≤ perTerm ≤ courseCount
  • The prerequisite graph is acyclic and has no duplicate pairs.

Hint

Show the first hint

Greedy choices fail: which free courses you take first matters (see example 2). With at most 13 courses, what can you enumerate?

Walkthrough

How to approach it

01Clarify before coding

  • Can a course and its prerequisite be taken in the same semester? No, the prerequisite must be in an earlier semester.
  • Must every semester be full? No, at most perTerm courses.
  • Is there always a solution? Yes, the graph is acyclic.

02Brute force

BFS over passed-course masks, trying every non-empty subset of the available courses with at most perTerm members.

Cost: Correct, but subsets of every size are explored: up to 2^13 states times 2^13 subsets ≈ 6.7 · 10^7 transitions with heavy duplication.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.