Description Link to heading

1494. Parallel Courses II (Hard)

Solution Link to heading

This problem readily brings to mind the concept of topological sorting, followed by a greedy approach. However, this approach is erroneous! In essence, this problem is NP-Hard and can only be solved through brute force.

Let’s consider the application of state-compressed dynamic programming (DP). The subproblems are relatively straightforward to identify. We start by choosing $1, 2$, followed by selecting $3, 4, 5 $(meeting the prerequisites). We can use a binary number, $to$$study$, to represent the set of courses we currently need to study, and $pre[j]$ to represent the set of prerequisite courses for course $j$. The recursive function can be denoted as $dfs(to$$study, pre)$.

Within this recursive function, we first calculate the set of courses $tmp$ that can be studied at the moment:

for (int i = 0; i < n; ++i) {
    if ((((1 << i) & to_study) != 0) && (pre[i] & to_study) == 0) {
        // Indicates that i is in to_study and its prerequisite courses have been studied (or it has no prerequisites)
        tmp = (tmp | (1 << i));
        ++cnt;
    }
}

If the number of courses $cnt$ in $tmp$ is less than or equal to k, we can directly study all the courses in the $tmp$ set. Otherwise, we iterate through the subsets of $tmp$. If the number of courses $m$ in subset $i$ satisfies $m <= k$, we study that subset. In the next recursive call, the courses to be studied can be represented as $to$_$study \oplus i$.

For a method to enumerate subsets, refer to Bitwise Operations and Sets.

In C++, the library function to count the number of $1$ bits in a binary number is __builtin_popcount(i).

Code Link to heading 

class Solution {
  public:
    static auto dfs(int to_study, vector<int> &cache, int full, vector<int> &pre, int n, int k) -> int {
        if (to_study == 0) {
            return 0;
        }
        if (cache[to_study] != -1) {
            return cache[to_study];
        }
        int studied = (to_study ^ full);
        int count = 0; // Count the number of courses that can be studied
        int tmp = 0;   // Courses to be studied in this recursive call
        for (int i = 0; i < n; ++i) {
            if ((((1 << i) & to_study) != 0) && (pre[i] & to_study) == 0) {
                // Indicates that i is in to_study and its prerequisite courses have been studied (or it has no prerequisites)
                tmp = (tmp | (1 << i));
                ++count;
            }
        }
        if (count <= k) {
            cache[to_study] = dfs(to_study ^ tmp, cache, full, pre, n, k) + 1;
            return cache[to_study];
        }
        int result = INT_MAX;
        for (int i = tmp; i != 0; i = (i - 1) & tmp) {
            if (__builtin_popcount(i) <= k) {
                result = min(result, dfs(to_study ^ i, cache, full, pre, n, k) + 1);
            }
        }
        cache[to_study] = result;
        return cache[to_study];
    }

    int minNumberOfSemesters(int n, vector<vector<int>> &relations, int k) {
        vector<int> pre(n);
        for (auto &vec : relations) {
            int x = vec[0] - 1, y = vec[1] - 1; // Adjusting indices to start from 0 to n-1
            pre[y] = (pre[y] | (1 << x));
        }
        int full = (1 << n) - 1; // Full set
        vector<int> cache(1 << n, -1);
        return dfs(full, cache, full, pre, n, k);
    }
};