Skip to content

1494. Parallel Courses II 👍

  • Time: $O(2^n \cdot n)$
  • Space: $O(2^n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
 public:
  int minNumberOfSemesters(int n, vector<vector<int>>& relations, int k) {
    // dp[i] := the minimum number of semesters to take the courses, where i is
    // the bitmask of the taken courses
    vector<int> dp(1 << n, n);
    // prereq[i] := the bitmask of all the dependencies of the i-th course
    vector<int> prereq(n);

    for (const vector<int>& relation : relations) {
      const int prevCourse = relation[0] - 1;
      const int nextCourse = relation[1] - 1;
      prereq[nextCourse] |= 1 << prevCourse;
    }

    dp[0] = 0;  // Don't need time to finish 0 course.

    for (int i = 0; i < dp.size(); ++i) {
      // the bitmask of all the courses can be taken
      int coursesCanBeTaken = 0;
      // Can take the j-th course if i contains all of j's prerequisites.
      for (int j = 0; j < n; ++j)
        if ((i & prereq[j]) == prereq[j])
          coursesCanBeTaken |= 1 << j;
      // Don't take any course which is already taken.
      // (i represents set of courses that are already taken)
      coursesCanBeTaken &= ~i;
      // Enumerate every bitmask subset of `coursesCanBeTaken`.
      for (unsigned s = coursesCanBeTaken; s > 0;
           s = (s - 1) & coursesCanBeTaken)
        if (popcount(s) <= k)
          // Any combination of courses (if <= k) can be taken now.
          // i | s := combining courses taken with courses can be taken.
          dp[i | s] = min(dp[i | s], dp[i] + 1);
    }

    return dp.back();
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
  public int minNumberOfSemesters(int n, int[][] relations, int k) {
    // dp[i] := the minimum number of semesters to take the courses, where i is
    // the bitmask of the taken courses
    int[] dp = new int[1 << n];
    Arrays.fill(dp, n);
    // prereq[i] := the bitmask of all the dependencies of the i-th course
    int[] prereq = new int[n];

    for (int[] r : relations) {
      final int prevCourse = r[0] - 1;
      final int nextCourse = r[1] - 1;
      prereq[nextCourse] |= 1 << prevCourse;
    }

    dp[0] = 0; // Don't need time to finish 0 course.

    for (int i = 0; i < dp.size(); ++i) {
      // the bitmask of all the courses can be taken
      int coursesCanBeTaken = 0;
      // Can take the j-th course if i contains all of j's prerequisites.
      for (int j = 0; j < n; ++j)
        if ((i & prereq[j]) == prereq[j])
          coursesCanBeTaken |= 1 << j;
      // Don't take any course which is already taken.
      // (i represents set of courses that are already taken)
      coursesCanBeTaken &= ~i;
      // Enumerate every bitmask subset of `coursesCanBeTaken`.
      for (int s = coursesCanBeTaken; s > 0; s = (s - 1) & coursesCanBeTaken)
        if (Integer.bitCount(s) <= k)
          // Any combination of courses (if <= k) can be taken now.
          // i | s := combining courses taken with courses can be taken.
          dp[i | s] = Math.min(dp[i | s], dp[i] + 1);
    }

    return dp[(1 << n) - 1];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
  def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:
    # dp[i] := the minimum number of semesters to take the courses, where i is
    # the bitmask of the taken courses
    dp = [n] * (1 << n)
    # prereq[i] := bitmask of all dependencies of course i
    prereq = [0] * n

    for prevCourse, nextCourse in relations:
      prereq[nextCourse - 1] |= 1 << prevCourse - 1

    dp[0] = 0  # Don't need time to finish 0 course.

    for i in range(1 << n):
      # the bitmask of all the courses can be taken
      coursesCanBeTaken = 0
      # Can take the j-th course if i contains all of j's prerequisites.
      for j in range(n):
        if (i & prereq[j]) == prereq[j]:
          coursesCanBeTaken |= 1 << j
      # Don't take any course which is already taken.
      # (i represents set of courses that are already taken)
      coursesCanBeTaken &= ~i
      # Enumerate every bitmask subset of `coursesCanBeTaken`.
      s = coursesCanBeTaken
      while s:
        if s.bit_count() <= k:
          # Any combination of courses (if <= k) can be taken now.
          # i | s := combining courses taken with courses can be taken.
          dp[i | s] = min(dp[i | s], dp[i] + 1)
        s = (s - 1) & coursesCanBeTaken

    return dp[-1]