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 k it means we can take more than K .But we cant take more than k and taking less than k will not be optimal . So we will try to take all the combination of available courses . Now the magic of bitmask will happen . Suppose we have 1011001 as ok means we can take 1st , 3rd , 4th & 7th course . Now what will be the all combination 1011001 0011001 1001001 1010001 1011000 0001001 1000001 1010000 0010001 0011000 1001000 1010000 1000000 0001000 0010000 0000001 I may have miss 1 or 2 but you understood i guess. So how can we produce this Well i prefer to see this following post and learn about submask of bitmask Here

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

All Problems

All Solutions