## 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] = [x`

represents a prerequisite relationship, that is, the course _{i}, y_{i}]`x`

must be taken before the course _{i}`y`

. Also, you are given the integer _{i}`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 = 2Output:3Explanation: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 = 2Output:4Explanation: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 = 2Output:6

**Constraints:**

`1 <= n <= 15`

`1 <= k <= n`

`0 <= dependencies.length <= n * (n-1) / 2`

`dependencies[i].length == 2`

`1 <= x`

_{i}, y_{i}<= n`x`

_{i}!= y_{i}- All prerequisite relationships are distinct, that is,
`dependencies[i] != dependencies[j]`

. - The given graph is a directed acyclic graph.

## Rust Solution

```
struct Solution;
struct Solver {
n: usize,
k: usize,
pre: Vec<u32>,
memo: Vec<i32>,
}
impl Solver {
fn new(n: usize, k: usize, pre: Vec<u32>) -> Self {
let mut memo: Vec<i32> = vec![-1; (1 << n) as usize];
memo[0] = 0;
Solver { n, k, pre, memo }
}
fn dfs(&self, k: usize, cur: u32, available: u32, groups: &mut Vec<u32>) {
if k == 0 {
groups.push(cur);
}
if available != 0 && k > 0 {
let bit = 1 << available.trailing_zeros();
self.dfs(k - 1, cur | bit, available & !bit, groups);
self.dfs(k, cur, available & !bit, groups);
}
}
fn dp(&mut self, left: u32) -> i32 {
if self.memo[left as usize] != -1 {
self.memo[left as usize]
} else {
let mut available: u32 = 0;
for i in 0..self.n {
if left & 1 << i != 0 && self.pre[i] & left == 0 {
available |= 1 << i;
}
}
let res = if available.count_ones() <= self.k as u32 {
1 + self.dp(left & !available)
} else {
let mut groups: Vec<u32> = vec![];
self.dfs(self.k, 0, available, &mut groups);
groups
.into_iter()
.map(|g| 1 + self.dp(left & !g))
.min()
.unwrap()
};
self.memo[left as usize] = res;
res
}
}
}
impl Solution {
fn min_number_of_semesters(n: i32, dependencies: Vec<Vec<i32>>, k: i32) -> i32 {
let n = n as usize;
let k = k as usize;
let mut pre = vec![0; n];
for dependency in dependencies {
let x = dependency[0] as usize - 1;
let y = dependency[1] as usize - 1;
pre[y] |= 1 << x;
}
let mut solver = Solver::new(n, k, pre);
solver.dp((1 << n) - 1)
}
}
#[test]
fn test() {
let n = 4;
let dependencies = vec_vec_i32![[2, 1], [3, 1], [1, 4]];
let k = 2;
let res = 3;
assert_eq!(Solution::min_number_of_semesters(n, dependencies, k), res);
let n = 5;
let dependencies = vec_vec_i32![[2, 1], [3, 1], [4, 1], [1, 5]];
let k = 2;
let res = 4;
assert_eq!(Solution::min_number_of_semesters(n, dependencies, k), res);
let n = 11;
let dependencies = vec_vec_i32![];
let k = 2;
let res = 6;
assert_eq!(Solution::min_number_of_semesters(n, dependencies, k), res);
}
```

Having problems with this solution? Click here to submit an issue on github.