Advantage Shuffle
Description
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
.
Example 1:
Input: A = [2,7,11,15], B = [1,10,4,11]
Output: [2,11,7,15]
Example 2:
Input: A = [12,24,8,32], B = [13,25,32,11]
Output: [24,32,8,12]
Note:
1 <= A.length = B.length <= 10000
0 <= A[i] <= 10^9
0 <= B[i] <= 10^9
Solution
class Solution {
public:
vector<int> advantageCount(vector<int>& A, vector<int>& B) {
int n = A.size();
vector<int> ans(n, -1);
multiset<int> nums(A.begin(), A.end());
for(int i = 0; i < n; ++i){
auto it = nums.upper_bound(B[i]);
if(it != nums.end()){
ans[i] = *it;
nums.erase(it);
}
}
auto it = nums.begin();
for(int i = 0; i < n; ++i){
if(ans[i] < 0){
ans[i] = *it;
++it;
}
}
return ans;
}
};
Last updated