https://leetcode.com/problems/parallel-courses-ii

There are a lot of not-working greedy solutions for this problem, but I think the only one truly correct way to solve it is to use binary masks, see similarity with Travelling Salesman Problem. (see https://en.wikipedia.org/wiki/Travelling_salesman_problem and https://en.wikipedia.org/wiki/Held%E2%80%93Karp_algorithm)

Let us denote by dp[i][j] tuple with:

  1. minumum number of days we need to finish
  2. number of non-zero bits for binary mask of the last semester
  3. binary mask of the last semester

all courses denoted by binary mask i and such that the last course we take is j. For example for dp[13][3], i=13 is represented as 1101, and it means that we take courses number 0, 2, 3 and the last one we take is number 3. (instead of starting with 1, let us subtract 1 from all courses and start from 0).

Let us also introduce bm_dep[i]: this will be binary mask for all courses we need to take, before we can take course number i. For example bm_dep[3] = 6 = 110 means, that we need to take courses 1 and 2 before we can take course number 3.

Now, let us iterate over all i in range(1<<n). Let us evaluate n_z_bit, this will be an array with all places with non-zero bits. For example for i=13=1101, n_z_bit = [0,2,3].

What we need to do next, we:

  1. First check that we really can take new course number j, using bm_dep[j] & i == bm_dep[j].
  2. Now, we want to update dp[i][j], using dp[i^(1<<j)][t], for example if we want to find answer for (1,3,4,5) courses with 3 being the last course, it means that we need to look into (1,4,5) courses, where we add course 3.
  3. We check how many courses we already take in last semester, using bits < k, and also make sure, that we can add new course to last semester. Now we have two candidates: (cand, bits + 1, mask + (1<<j)) and dp[i][j] and we need to choose the best one. In other case, we need to take new semester: so cands will be equalt to cands + 1, bits will be equal to 1 and binary mask for last semester is 1<<j.

Complexity is O(n^2*2^n), because we iterate all bitmasks and then we iterate over all pairs of non-zero bit, and we have O(n^2) of them. Memory is O(2^n * n). I think it can be simplified to O(n*2^n)/O(2^n) complexity, but I am not sure yet.

class Solution:
    def minNumberOfSemesters(self, n, dependencies, k):
        dp = [[(100, 0, 0)] * n for _ in range(1<<n)]
        
        bm_dep = [0]*(n)
        for i,j in dependencies:
            bm_dep[j-1]^=(1<<(i-1))

        for i in range(n):
            if bm_dep[i] == 0: dp[1<<i][i] = (1, 1, 1<<i)
        
        for i in range(1<<n):
            n_z_bits = [len(bin(i))-p-1 for p,c in enumerate(bin(i)) if c=="1"]
                    
            for t, j in permutations(n_z_bits, 2):
                if bm_dep[j] & i == bm_dep[j]:
                    cand, bits, mask = dp[i^(1<<j)][t]
                    if bm_dep[j] & mask == 0 and bits < k:
                        dp[i][j] = min(dp[i][j], (cand, bits + 1, mask + (1<<j)))
                    else:
                        dp[i][j] = min(dp[i][j], (cand+1, 1, 1<<j))
                                          
        return min([i for i, j, k in dp[-1]])

If you like the solution, you can upvote it on leetcode discussion section: Problem 1494