1583. Count Unhappy Friends Medium

1/**
2 * [1583] Count Unhappy Friends
3 *
4 * You are given a list of preferences for n friends, where n is always even.
5 * For each person i, preferences[i] contains a list of friends sorted in the order of preference. In other words, a friend earlier in the list is more preferred than a friend later in the list. Friends in each list are denoted by integers from 0 to n-1.
6 * All the friends are divided into pairs. The pairings are given in a list pairs, where pairs[i] = [xi, yi] denotes xi is paired with yi and yi is paired with xi.
7 * However, this pairing may cause some of the friends to be unhappy. A friend x is unhappy if x is paired with y and there exists a friend u who is paired with v but:
8 * 
9 * 	x prefers u over y, and
10 * 	u prefers x over v.
11 * 
12 * Return the number of unhappy friends.
13 *  
14 * Example 1:
15 * 
16 * Input: n = 4, preferences = [[1, 2, 3], [3, 2, 0], [3, 1, 0], [1, 2, 0]], pairs = [[0, 1], [2, 3]]
17 * Output: 2
18 * Explanation:
19 * Friend 1 is unhappy because:
20 * - 1 is paired with 0 but prefers 3 over 0, and
21 * - 3 prefers 1 over 2.
22 * Friend 3 is unhappy because:
23 * - 3 is paired with 2 but prefers 1 over 2, and
24 * - 1 prefers 3 over 0.
25 * Friends 0 and 2 are happy.
26 * 
27 * Example 2:
28 * 
29 * Input: n = 2, preferences = [[1], [0]], pairs = [[1, 0]]
30 * Output: 0
31 * Explanation: Both friends 0 and 1 are happy.
32 * 
33 * Example 3:
34 * 
35 * Input: n = 4, preferences = [[1, 3, 2], [2, 3, 0], [1, 3, 0], [0, 2, 1]], pairs = [[1, 3], [0, 2]]
36 * Output: 4
37 * 
38 *  
39 * Constraints:
40 * 
41 * 	2 <= n <= 500
42 * 	n is even.
43 * 	preferences.length == n
44 * 	preferences[i].length == n - 1
45 * 	0 <= preferences[i][j] <= n - 1
46 * 	preferences[i] does not contain i.
47 * 	All values in preferences[i] are unique.
48 * 	pairs.length == n/2
49 * 	pairs[i].length == 2
50 * 	xi != yi
51 * 	0 <= xi, yi <= n - 1
52 * 	Each person is contained in exactly one pair.
53 * 
54 */
55pub struct Solution {}
56
57// problem: https://leetcode.com/problems/count-unhappy-friends/
58// discuss: https://leetcode.com/problems/count-unhappy-friends/discuss/?currentPage=1&orderBy=most_votes&query=
59
60// submission codes start here
61
62impl Solution {
63    pub fn unhappy_friends(n: i32, preferences: Vec<Vec<i32>>, pairs: Vec<Vec<i32>>) -> i32 {
64        0
65    }
66}
67
68// submission codes end
69
70#[cfg(test)]
71mod tests {
72    use super::*;
73
74    #[test]
75    fn test_1583() {
76    }
77}
78