Leetcode 1583. Count Unhappy Friends
You are given a list of preferences for n friends, where n is always even.For each person i, preferences 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.
All the friends are divided into pairs. The pairings are given in a list pairs, where pairs = denotes xi is paired with yi and yi is paired with xi.
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:
x prefers u over y, and
u prefers x over v.
Return the number of unhappy friends.
Example 1:
Input: n = 4, preferences = [, , , ], pairs = [, ]
Output: 2
Explanation:
Friend 1 is unhappy because:
- 1 is paired with 0 but prefers 3 over 0, and
- 3 prefers 1 over 2.
Friend 3 is unhappy because:
- 3 is paired with 2 but prefers 1 over 2, and
- 1 prefers 3 over 0.
Friends 0 and 2 are happy.
Example 2:
Input: n = 2, preferences = [, ], pairs = []
Output: 0
Explanation: Both friends 0 and 1 are happy.
Example 3:
Input: n = 4, preferences = [, , , ], pairs = [, ]
Output: 4
Constraints:
2 <= n <= 500
n is even.
preferences.length == n
preferences.length == n - 1
0 <= preferences <= n - 1
preferences does not contain i.
All values in preferences are unique.
pairs.length == n/2
pairs.length == 2
xi != yi
0 <= xi, yi <= n - 1
Each person is contained in exactly one pair.
class Solution:
def unhappyFriends(self, n: int, preferences: List], pairs: List]) -> int:
hashmap = collections.defaultdict(lambda: collections.defaultdict(int))
for i in range(len(preferences)):
for j in range(len(preferences)):
first = i
second = preferences
idx = j
hashmap = idx
unhappy = * n
m = len(pairs)
for i in range(m):
x = pairs
y = pairs
x_y_prefer, y_x_prefer = hashmap, hashmap
for j in range(i + 1, m):
u = pairs
v = pairs
x_u_prefer, x_v_prefer = hashmap, hashmap
y_u_prefer, y_v_prefer = hashmap, hashmap
u_v_prefer, u_x_prefer, u_y_prefer = hashmap, hashmap, hashmap
v_u_prefer, v_x_prefer, v_y_prefer = hashmap, hashmap, hashmap
if x_u_prefer < x_y_prefer and u_x_prefer < u_v_prefer:
unhappy = unhappy = 1
if y_v_prefer < y_x_prefer and v_y_prefer < v_u_prefer:
unhappy = unhappy = 1
if x_v_prefer < x_y_prefer and v_x_prefer < v_u_prefer:
unhappy = unhappy = 1
if y_u_prefer < y_x_prefer and u_y_prefer < u_v_prefer:
unhappy = unhappy = 1
return sum(unhappy)
页:
[1]