# 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

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;
}
}
```