Parallel Courses II LeetCode Solution

Difficulty Level Hard
Frequently asked in Google MicrosoftViews 2071

Table of Contents

Problem Statement

Parallel Courses II LeetCode Solution- You are given an integer `n`, which indicates that there are `n` courses labeled from `1` to `n`. You are also given an array `relations` where `relations[i] = [prevCourse`i`, nextCourse`i`]`, representing a prerequisite relationship between course `prevCourse`i and course `nextCourse`i: course `prevCourse`i have to be taken before the course `nextCourse`i. 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 in the previous semester for the courses you are taking.

Return the minimum number of semesters needed to take all courses. The test cases will be generated such that it is possible to take every course.

```Input: n = 4, dependencies = [[2,1],[3,1],[1,4]], k = 2
Output: 3
Explanation: The figure above represents the given graph.
In the first semester, you can take courses 2 and 3.
In the second semester, you can take course 1.
In the third semester, you can take course 4.```

Explanation

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

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

all courses denoted by the 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 the 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 a 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 the course number `3`.

Now, let us iterate overall `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 :

1. First, check that we really can take a 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 answers 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 a course `3`.
3. We check how many courses we already take in the last semester, using, and also make sure, that we can add a new course to the 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 another case, we need to take a new semester: so `cands` will be equal to `cands + 1``bits` will be equal to `1` and binary mask for last semester is `1<<j`.

Code

Java Code for Parallel Courses II

```class Solution {
public int minNumberOfSemesters(int n, int[][] relations, int k) {
int[] prereq = new int[n];
for (int[] req : relations) {
prereq[req[1] - 1] |= 1 << (req[0] - 1);
}
int[] dp = new int[(1 << n)];
Arrays.fill(dp, -1);
return solve(0, n, k, prereq, dp);
}

private int solve(int mask, int n, int k, int[] prereq, int[] dp) {
if (mask == (1 << n) - 1) {
return 0;
}
if (dp[mask] != -1) {
return dp[mask];
}
int availableCourses = 0;
for (int i = 0; i < n; i += 1) {
if ((mask & prereq[i]) == prereq[i]) {
if( (mask & (1<<i))>0 )
continue;
availableCourses |= 1 << i;
}
}
int best = Integer.MAX_VALUE / 2;
for (int submask = availableCourses; submask > 0; submask = (submask - 1) & availableCourses) {
if (Integer.bitCount(submask) <= k) {
best = Math.min(best, 1 + solve(mask | submask, n, k, prereq, dp));
}
}
return dp[mask] = best;
}
}```

Python Code for Parallel Courses II

```class Solution:
def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:
self.degree = [0] * n
memo = collections.defaultdict(list)
for i,j in relations:
memo[i - 1] += j - 1,
self.degree[j - 1] += 1
@lru_cache(None)
def solve(mask):
if mask == (1 << n) - 1:
return 0
take = []
for i in range(n):
if not mask & 1 << i and self.degree[i] == 0:
take += i,
ans = float('inf')
for i in combinations(take, min(k, len(take))):
temp = mask
for j in i:
temp |= 1 << j
for a in memo[j]:
self.degree[a] -= 1
ans = min(ans, 1 + solve(temp))
for j in i:
for a in memo[j]:
self.degree[a] += 1
return ans
return solve(0)```

O(3^n)

O(n)

Translate »