1494. Parallel Courses II Hard

1/**
2 * [1494] Parallel Courses II
3 *
4 * 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] = [prevCoursei, nextCoursei], representing a prerequisite relationship between course prevCoursei and course nextCoursei: course prevCoursei has to be taken before course nextCoursei. Also, you are given the integer k.
5 * In one semester, you can take at most k courses as long as you have taken all the prerequisites in the previous semesters for the courses you are taking.
6 * Return the minimum number of semesters needed to take all courses. The testcases will be generated such that it is possible to take every course.
7 *  
8 * Example 1:
9 * <img alt="" src="https://assets.leetcode.com/uploads/2020/05/22/leetcode_parallel_courses_1.png" style="width: 269px; height: 147px;" />
10 * Input: n = 4, relations = [[2,1],[3,1],[1,4]], k = 2
11 * Output: 3
12 * Explanation: The figure above represents the given graph.
13 * In the first semester, you can take courses 2 and 3.
14 * In the second semester, you can take course 1.
15 * In the third semester, you can take course 4.
16 * 
17 * Example 2:
18 * <img alt="" src="https://assets.leetcode.com/uploads/2020/05/22/leetcode_parallel_courses_2.png" style="width: 271px; height: 211px;" />
19 * Input: n = 5, relations = [[2,1],[3,1],[4,1],[1,5]], k = 2
20 * Output: 4
21 * Explanation: The figure above represents the given graph.
22 * In the first semester, you can only take courses 2 and 3 since you cannot take more than two per semester.
23 * In the second semester, you can take course 4.
24 * In the third semester, you can take course 1.
25 * In the fourth semester, you can take course 5.
26 * 
27 *  
28 * Constraints:
29 * 
30 * 	1 <= n <= 15
31 * 	1 <= k <= n
32 * 	0 <= relations.length <= n * (n-1) / 2
33 * 	relations[i].length == 2
34 * 	1 <= prevCoursei, nextCoursei <= n
35 * 	prevCoursei != nextCoursei
36 * 	All the pairs [prevCoursei, nextCoursei] are unique.
37 * 	The given graph is a directed acyclic graph.
38 * 
39 */
40pub struct Solution {}
41
42// problem: https://leetcode.com/problems/parallel-courses-ii/
43// discuss: https://leetcode.com/problems/parallel-courses-ii/discuss/?currentPage=1&orderBy=most_votes&query=
44
45// submission codes start here
46
47impl Solution {
48    pub fn min_number_of_semesters(n: i32, relations: Vec<Vec<i32>>, k: i32) -> i32 {
49        0
50    }
51}
52
53// submission codes end
54
55#[cfg(test)]
56mod tests {
57    use super::*;
58
59    #[test]
60    fn test_1494() {
61    }
62}
63