Minimum Semesters with Prerequisites and a Course Limit

### Problem Courses are labeled 1..n. Each relation[prev,next] requires prev to be completed in an earlier semester than next. Take at most k courses per semester,only after all their prerequisites have been completed in previous semesters. Return the minimum semesters to finish every course. The prerequisite graph is a DAG. ```cpp class Solution { public: int minNumberOfSemesters(int n, vector<vector<int>>& relations, int k); }; ``` ### Examples **Example 1:** ```text Input: n = 3, relations = [[1,3],[2,3]], k = 2 Output: 2 Explanation: Take1 and2 together,then3. Course3 cannot share their semester. ``` **Example 2:** ```text Input: n = 4, relations = [], k = 3 Output: 2 Explanation: Four courses exceed one semester's capacity3; any three followed by the last finish in two. ``` ### Constraints - `1 <= n <= 15` and `1 <= k <= n`. - There are 0 to n*(n-1)/2 unique prerequisite pairs,each with two different labels in `[1,n]`. - The directed graph is acyclic and all courses can be completed. ### Contract considerations The DAG guarantee makes completion possible; the output is the minimum count,not a course schedule. ```hint Read the boundary condition Prerequisites must be completed in earlier semesters. Include independent courses, capacity limits, and competing choices of currently available courses. ``` ### Boundary reminders The DAG guarantee makes completion possible; the output is the minimum count,not a course schedule.