870. Advantage Shuffle
Given two arrays A and B of equal size, the advantage of A with respect to B is the number of indices i for which A[i] > B[i].
Return any permutation of A that maximizes its advantage with respect to B.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
vector<int> advantageCount(vector<int>& A, vector<int>& B) {
multiset<int> s(A.begin(), A.end());
vector<int> res(A.size(), -1);
for(int i = 0; i < A.size(); i++) {
auto it = s.upper_bound(B[i]);
if(it == s.end()) continue;
res[i] = *it;
s.erase(it);
}
for(int i = 0; i < A.size(); i++) {
if(res[i] == -1) {
res[i] = *s.rbegin();
s.erase(prev(s.end()));
}
}
return res;
}
};
|
