comments | difficulty | edit_url | rating | source | tags | ||
---|---|---|---|---|---|---|---|
true |
Medium |
1658 |
Weekly Contest 206 Q2 |
|
You are given a list of preferences
for n
friends, where n
is always even.
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
.
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
.
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
prefersu
overy
, andu
prefersx
overv
.
Return the number of unhappy friends.
Example 1:
Input: n = 4, preferences = [[1, 2, 3], [3, 2, 0], [3, 1, 0], [1, 2, 0]], pairs = [[0, 1], [2, 3]] 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 = [[1], [0]], pairs = [[1, 0]] Output: 0 Explanation: Both friends 0 and 1 are happy.
Example 3:
Input: n = 4, preferences = [[1, 3, 2], [2, 3, 0], [1, 3, 0], [0, 2, 1]], pairs = [[1, 3], [0, 2]] Output: 4
Constraints:
2 <= n <= 500
n
is even.preferences.length == n
preferences[i].length == n - 1
0 <= preferences[i][j] <= n - 1
preferences[i]
does not containi
.- All values in
preferences[i]
are unique. pairs.length == n/2
pairs[i].length == 2
xi != yi
0 <= xi, yi <= n - 1
- Each person is contained in exactly one pair.
We use an array
We enumerate each friend
After the enumeration, we obtain the number of unhappy friends.
The time complexity is
class Solution:
def unhappyFriends(
self, n: int, preferences: List[List[int]], pairs: List[List[int]]
) -> int:
d = [{x: j for j, x in enumerate(p)} for p in preferences]
p = {}
for x, y in pairs:
p[x] = y
p[y] = x
ans = 0
for x in range(n):
y = p[x]
for i in range(d[x][y]):
u = preferences[x][i]
v = p[u]
if d[u][x] < d[u][v]:
ans += 1
break
return ans
class Solution {
public int unhappyFriends(int n, int[][] preferences, int[][] pairs) {
int[][] d = new int[n][n];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n - 1; ++j) {
d[i][preferences[i][j]] = j;
}
}
int[] p = new int[n];
for (var e : pairs) {
int x = e[0], y = e[1];
p[x] = y;
p[y] = x;
}
int ans = 0;
for (int x = 0; x < n; ++x) {
int y = p[x];
for (int i = 0; i < d[x][y]; ++i) {
int u = preferences[x][i];
int v = p[u];
if (d[u][x] < d[u][v]) {
++ans;
break;
}
}
}
return ans;
}
}
class Solution {
public:
int unhappyFriends(int n, vector<vector<int>>& preferences, vector<vector<int>>& pairs) {
vector<vector<int>> d(n, vector<int>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n - 1; ++j) {
d[i][preferences[i][j]] = j;
}
}
vector<int> p(n, 0);
for (auto& e : pairs) {
int x = e[0], y = e[1];
p[x] = y;
p[y] = x;
}
int ans = 0;
for (int x = 0; x < n; ++x) {
int y = p[x];
for (int i = 0; i < d[x][y]; ++i) {
int u = preferences[x][i];
int v = p[u];
if (d[u][x] < d[u][v]) {
++ans;
break;
}
}
}
return ans;
}
};
func unhappyFriends(n int, preferences [][]int, pairs [][]int) (ans int) {
d := make([][]int, n)
for i := range d {
d[i] = make([]int, n)
}
for i := 0; i < n; i++ {
for j := 0; j < n-1; j++ {
d[i][preferences[i][j]] = j
}
}
p := make([]int, n)
for _, e := range pairs {
x, y := e[0], e[1]
p[x] = y
p[y] = x
}
for x := 0; x < n; x++ {
y := p[x]
for i := 0; i < d[x][y]; i++ {
u := preferences[x][i]
v := p[u]
if d[u][x] < d[u][v] {
ans++
break
}
}
}
return
}
function unhappyFriends(n: number, preferences: number[][], pairs: number[][]): number {
const d: number[][] = Array.from({ length: n }, () => Array(n).fill(0));
for (let i = 0; i < n; ++i) {
for (let j = 0; j < n - 1; ++j) {
d[i][preferences[i][j]] = j;
}
}
const p: number[] = Array(n).fill(0);
for (const [x, y] of pairs) {
p[x] = y;
p[y] = x;
}
let ans = 0;
for (let x = 0; x < n; ++x) {
const y = p[x];
for (let i = 0; i < d[x][y]; ++i) {
const u = preferences[x][i];
const v = p[u];
if (d[u][x] < d[u][v]) {
++ans;
break;
}
}
}
return ans;
}