### Leetcode

• Time:O(n\log n)
• Space:O(n)

## C++

``````class Solution {
public:
vector<int> advantageCount(vector<int>& A, vector<int>& B) {
multiset<int> set{begin(A), end(A)};

for (int i = 0; i < B.size(); ++i) {
auto p = *rbegin(set) <= B[i] ? begin(set) : set.upper_bound(B[i]);
A[i] = *p;
set.erase(p);
}

return A;
}
};
``````

## JAVA

``````class Solution {
public int[] advantageCount(int[] A, int[] B) {
TreeMap<Integer, Integer> map = new TreeMap<>();

for (int a : A)
map.put(a, map.getOrDefault(a, 0) + 1);

for (int i = 0; i < B.length; i++) {
Integer key = map.higherKey(B[i]);
if (key == null)
key = map.firstKey();
map.put(key, map.get(key) - 1);
if (map.get(key) == 0)
map.remove(key);
A[i] = key;
}

return A;
}
}
``````

## Python

``````from sortedcontainers import SortedList

class Solution:
def advantageCount(self, A: List[int], B: List[int]) -> List[int]:
sl = SortedList(A)

for i, b in enumerate(B):
index = 0 if sl[-1] <= b else sl.bisect_right(b)
A[i] = sl[index]
del sl[index]

return A
``````