1203. Sort Items by Groups Respecting Dependencies Hard

1/**
2 * [1203] Sort Items by Groups Respecting Dependencies
3 *
4 * There are n items each belonging to zero or one of m groups where group[i] is the group that the i-th item belongs to and it's equal to -1 if the i-th item belongs to no group. The items and the groups are zero indexed. A group can have no item belonging to it.
5 * Return a sorted list of the items such that:
6 * 
7 * 	The items that belong to the same group are next to each other in the sorted list.
8 * 	There are some relations between these items where beforeItems[i] is a list containing all the items that should come before the i-th item in the sorted array (to the left of the i-th item).
9 * 
10 * Return any solution if there is more than one solution and return an empty list if there is no solution.
11 *  
12 * Example 1:
13 * <img alt="" src="https://assets.leetcode.com/uploads/2019/09/11/1359_ex1.png" style="width: 191px; height: 181px;" />
14 * 
15 * Input: n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3,6],[],[],[]]
16 * Output: [6,3,4,1,5,2,0,7]
17 * 
18 * Example 2:
19 * 
20 * Input: n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3],[],[4],[]]
21 * Output: []
22 * Explanation: This is the same as example 1 except that 4 needs to be before 6 in the sorted list.
23 * 
24 *  
25 * Constraints:
26 * 
27 * 	1 <= m <= n <= 3 * 10^4
28 * 	group.length == beforeItems.length == n
29 * 	-1 <= group[i] <= m - 1
30 * 	0 <= beforeItems[i].length <= n - 1
31 * 	0 <= beforeItems[i][j] <= n - 1
32 * 	i != beforeItems[i][j]
33 * 	beforeItems[i] does not contain duplicates elements.
34 * 
35 */
36pub struct Solution {}
37
38// problem: https://leetcode.com/problems/sort-items-by-groups-respecting-dependencies/
39// discuss: https://leetcode.com/problems/sort-items-by-groups-respecting-dependencies/discuss/?currentPage=1&orderBy=most_votes&query=
40
41// submission codes start here
42
43impl Solution {
44    pub fn sort_items(n: i32, m: i32, group: Vec<i32>, before_items: Vec<Vec<i32>>) -> Vec<i32> {
45        vec![]
46    }
47}
48
49// submission codes end
50
51#[cfg(test)]
52mod tests {
53    use super::*;
54
55    #[test]
56    fn test_1203() {
57    }
58}
59