Parallel Courses II

Given the integer n representing the number of courses at some university labeled from 1 to n, and the array dependencies where dependencies[i] = [xi, yi]  represents a prerequisite relationship, that is, the course xi must be taken before the course yi.  Also, you are given the integer k.

In one semester you can take at most k courses as long as you have taken all the prerequisites for the courses you are taking.

Return the minimum number of semesters to take all courses. It is guaranteed that you can take all courses in some way.

 

Example 1:

Input: n = 4, dependencies = [[2,1],[3,1],[1,4]], k = 2
Output: 3 
Explanation: The figure above represents the given graph. In this case we can take courses 2 and 3 in the first semester, then take course 1 in the second semester and finally take course 4 in the third semester.

Example 2:

Input: n = 5, dependencies = [[2,1],[3,1],[4,1],[1,5]], k = 2
Output: 4 
Explanation: The figure above represents the given graph. In this case one optimal way to take all courses is: take courses 2 and 3 in the first semester and take course 4 in the second semester, then take course 1 in the third semester and finally take course 5 in the fourth semester.

Example 3:

Input: n = 11, dependencies = [], k = 2
Output: 6

 

Constraints:


Solution:

class Solution {
    public int minNumberOfSemesters(int n, int[][] dependencies, int k) {
        // step 1. save the courses we need to take as integer
        // e.x.) if prerequisites for course 2 are courses 0 and 3 store integer value of `1001` to prerequisites[2]
        int[] prerequisites = new int[n];
        for (int[] dependency: dependencies)
            prerequisites[dependency[1] - 1] |= 1 << (dependency[0] - 1);

        // step 2. dp[courses] = what is the minimum number of days it takes to finish the course given that we have the `courses` left to take?
        int[] dp = new int[1 << n];
        Arrays.fill(dp, n + 1); // fill with the dp array with arbitrary values not possible to exceed
        dp[0] = 0; // no courses left to take == no more semester necessary

        for (int i = 0; i < (1 << n); i++) {
            // i = courses we have taken
            int availableCourses = 0; // courses we can take in the semester given we took
            for (int course = 0; course < n; course++)
                if ((prerequisites[course] & i) == prerequisites[course])
                    // if `i` courses (the courses we already have taken) contain all prerequisites for `course`, add it to `availableCourses`
                    availableCourses |= 1 << course;
            availableCourses &= ~i; // remove the courses we have already taken
            for (int nextSemester = availableCourses; nextSemester > 0; nextSemester = (nextSemester - 1) & availableCourses) {
                // iterate throught the subsets of available courses we can take next
                // nextSemester = courses we choose to take next semester;
                if (Integer.bitCount(nextSemester) <= k) // # courses must be <= k
                    dp[i | nextSemester] = Math.min(dp[i | nextSemester], 1 + dp[i]);
            }
        }

        return dp[(1 << n) - 1]; //  since the problem assumes it is possible, I am not considering a corner case where the courses are impossible to finish
    }
}