Question
Formatted question description: https://leetcode.ca/all/1494.html
1494. 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:
1 <= n <= 15
1 <= k <= n
0 <= dependencies.length <= n * (n-1) / 2
dependencies[i].length == 2
1 <= xi, yi <= n
xi != yi
All prerequisite relationships are distinct, that is, dependencies[i] != dependencies[j].
The given graph is a directed acyclic graph.
Algorithm
Well this is a great problem to solve to understand the beauty of bitmask
First of all if you are thinking of making this AC by graph theory then you are wrong . This a NPC Problem (NP-complete problem) you cant solve it Polynomial time. There are some weak test in the problem thats it get AC even with graph theory approach . Basically you have to try every possible case for each day and each course.
How to do it?
Well we will use bitmask to solve this .
Now first of all we will need to take pre[i], that means pre[i] is a vector which will keep all the course that depend on ith course
for(int i=0;i<d.size();i++)
{
d[i][1]--;
d[i][0]--;
pre[d[i][0]].push_back(d[i][1]);
}
We decrease each node because that will help us in bitmasking as (1<<0)&m sets m’s 1st bit but (1«1)&m sets m’s 2nd bit
Now we will call a function that will solve it for use . As a parameter we will send how many courses are taken yet . Yes 0 courses are taken at the first
int minNumberOfSemesters(int N, vector<vector<int>>& d, int K) {
for(int i=0;i<d.size();i++)
{
d[i][1]--;
d[i][0]--;
pre[d[i][0]].push_back(d[i][1]);
}
return make(0);
Now the make function takes a parameter . we will call it mask (it is a integer) . Now does mask mean well if ith bit in the mask is 1 it means ith course is taken So if all the courses are taken then its done . Now if N=3 then (1«3) = 8(1000) and (1«3)-1 =7(111) So (1«n)-1 means all the n courses are taken . So if all the courses are taken then we need no more days to study
int make(int mask)
{
if(mask==(1<<n)-1)
return 0;
Now we will create an indegree vector . What does it stands for? Well indegree[i] means the number of course needs to be done before doing ith course
for(int i=0;i<n;i++)
{
if(mask&(1<<i)) // if this case is already taken . If you wonder but no course
continue; // is taken then wait its a recursion function , so in some
// call we may have took some course
for(int j=0;j<pre[i].size();j++) // increase indegree for all dependent course
{ // of i
indeg[pre[i][j]]++;
}
}
Now its easy to understand that the courses with 0 indegree and those who are not taken yet can be taken one this day . So we will create on more bitmask ok which will indicate the courses available . If the ith bit of ok is 1 then it means it can be taken on current day. int ok=0; // first of all no course can be taken
for(int i=0;i<n;i++)
{
if(indeg[i]==0&&!(mask&(1<<i))) // no dependency and not taken yet
{
ok|=(1<<i); // i guess you know or function
}
}
Now the number of set bit in ok is the number of course can be taken on this day. We can count the number of set by a builtin function __builtin_popcount(ok) . int available_course=__builtin_popcount(ok);
Great Now there can be 2 cases 1 where available_courses
So we will make all the subset mask of ok and try to solve for all remaining courses
for(int j=ok;j;j=(j-1)&ok)
{
int took=__builtin_popcount(j);
if(took!=k) // cant take or not optimal
continue;
else
{
taken=min(taken,1+make(mask|j)); // +1 is for using this day
} // mask|j make all course in j taken
}
Now what about available courses <= k Well then taking all of them is optimal
if(available_course>k)
{
for(int j=ok;j;j=(j-1)&ok)
{
int took=__builtin_popcount(j);
if(took!=k)
continue;
else
{
taken=min(taken,1+make(mask|j));
}
}
}
else
{
taken=min(taken,1+make(mask|ok));
}
We can initialize taken=n+1 as it wont be more than n+1 as answer
Now few more thing left like memoization So we can simply take a DP[(1«(n+1)] because setting all courses will take (1«n)-1 space we may declare indgeree vector each time in the function . Also make vector 2D for pre[19]
Ref: https://sohojeprogramming.blogspot.com/2020/07/1494-parallel-courses-ii.html
Code
Java
public class Parallel_Courses_II {
class Solution {
public int minNumberOfSemesters(int n, int[][] deps, int k) {
int[] preq = new int[n];
for (int[] dep : deps) {
// to study j, what are the prerequisites? each set bit is a class that we need to take. ith bit means ith class
// -1 because classes are 1 to n
preq[dep[1] - 1] |= 1 << (dep[0] - 1);
}
int[] dp = new int[1 << n];
Arrays.fill(dp, n);
dp[0] = 0;
for (int i = 0; i < (1 << n); i++) {
// we are now at status i. we can "influence" a later status from this status
int canStudy = 0; // what are the classes we can study?
for (int j = 0; j < n; j++) {
// a & b== b means b is a's subset
// so if preq[j] is i's subset, we can now study j given status i
if ((i & preq[j]) == preq[j]) {
canStudy |= (1 << j);
}
}
canStudy &= ~i;
// take out i, so that we only enumerate a subset canStudy without i.
// note we will | later so here we need a set that has no intersection with i to reduce the enumeration cost
for (int sub = canStudy; sub > 0; sub = (sub - 1) & canStudy) {
// we can study one or more courses indicated by set "canStudy". we need to enumerate all non empty subset of it.
// This for loop is a typical way to enumerate all subsets of a given set "canStudy"
// we studied i using dp[i] semesters. now if we also study the subset sub, we need dp [i ]+1 semesters,
// and the status we can "influence" is dp[ i | sub] because at that state, we studied what we want to study in "sub"
if (Integer.bitCount(sub) <= k) {
dp[i | sub] = Math.min(dp[i | sub], dp[i] + 1);
}
}
}
return dp[(1 << n) - 1];
}
}
}Java
class Solution {
public int minNumberOfSemesters(int n, int[][] dependencies, int k) {
Map<Integer, Set<Integer>> nextMap = new HashMap<Integer, Set<Integer>>();
Map<Integer, Set<Integer>> prevMap = new HashMap<Integer, Set<Integer>>();
for (int[] dependency : dependencies) {
int course0 = dependency[0] - 1, course1 = dependency[1] - 1;
Set<Integer> set0 = nextMap.getOrDefault(course0, new HashSet<Integer>());
Set<Integer> set1 = prevMap.getOrDefault(course1, new HashSet<Integer>());
set0.add(course1);
set1.add(course0);
nextMap.put(course0, set0);
prevMap.put(course1, set1);
}
int[] indegrees = new int[n];
int[] outdegrees = new int[n];
Set<Integer> keySet = nextMap.keySet();
for (int course : keySet) {
Set<Integer> nextSet = nextMap.getOrDefault(course, new HashSet<Integer>());
Set<Integer> prevSet = prevMap.getOrDefault(course, new HashSet<Integer>());
for (int nextCourse : nextSet)
indegrees[nextCourse]++;
for (int prevCourse : prevSet)
outdegrees[prevCourse]++;
}
int[] tempIndegrees = new int[n];
int[] tempOutdegrees = new int[n];
System.arraycopy(indegrees, 0, tempIndegrees, 0, n);
System.arraycopy(outdegrees, 0, tempOutdegrees, 0, n);
int[] startSemesters = new int[n];
int semesters = 0;
Queue<Integer> queue = new LinkedList<Integer>();
for (int i = 0; i < n; i++) {
if (tempIndegrees[i] == 0)
queue.offer(i);
}
while (!queue.isEmpty()) {
semesters++;
int size = queue.size();
for (int i = 0; i < size; i++) {
int course = queue.poll();
startSemesters[course] = semesters;
Set<Integer> nextSet = nextMap.getOrDefault(course, new HashSet<Integer>());
for (int nextCourse : nextSet) {
tempIndegrees[nextCourse]--;
if (tempIndegrees[nextCourse] == 0)
queue.offer(nextCourse);
}
}
}
int[] endSemesters = new int[n];
for (int i = 0; i < n; i++) {
if (tempOutdegrees[i] == 0)
queue.offer(i);
}
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int course = queue.poll();
endSemesters[course] = semesters;
Set<Integer> prevSet = prevMap.getOrDefault(course, new HashSet<Integer>());
for (int prevCourse : prevSet) {
tempOutdegrees[prevCourse]--;
if (tempOutdegrees[prevCourse] == 0)
queue.offer(prevCourse);
}
}
semesters--;
}
int totalSemesters = 0;
PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>(new Comparator<Integer>() {
public int compare(Integer course0, Integer course1) {
if (startSemesters[course0] != startSemesters[course1])
return startSemesters[course0] - startSemesters[course1];
else
return endSemesters[course0] - endSemesters[course1];
}
});
for (int i = 0; i < n; i++) {
if (indegrees[i] == 0)
priorityQueue.offer(i);
}
while (!priorityQueue.isEmpty()) {
totalSemesters++;
int size = Math.min(priorityQueue.size(), k);
for (int i = 0; i < size; i++) {
int course = priorityQueue.poll();
Set<Integer> nextSet = nextMap.getOrDefault(course, new HashSet<Integer>());
for (int nextCourse : nextSet) {
indegrees[nextCourse]--;
if (indegrees[nextCourse] == 0)
priorityQueue.offer(nextCourse);
}
}
}
return totalSemesters;
}
}