<p>You are given two integer arrays <code>nums1</code> and <code>nums2</code> both of the same length. The <strong>advantage</strong> of <code>nums1</code> with respect to <code>nums2</code> is the number of indices <code>i</code> for which <code>nums1[i] &gt; nums2[i]</code>.</p>

<p>Return <em>any permutation of </em><code>nums1</code><em> that maximizes its <strong>advantage</strong> with respect to </em><code>nums2</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> nums1 = [2,7,11,15], nums2 = [1,10,4,11]
<strong>Output:</strong> [2,11,7,15]
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> nums1 = [12,24,8,32], nums2 = [13,25,32,11]
<strong>Output:</strong> [24,32,8,12]
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums1.length &lt;= 10<sup>5</sup></code></li>
	<li><code>nums2.length == nums1.length</code></li>
	<li><code>0 &lt;= nums1[i], nums2[i] &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution {
public:
    // For each B[i], we select the smallest number in A that is greater than B[i]. If there are no such number, we select the smallest number in A.
    // I am usign multiset to sort and keep track of numbers in A. After a number is selected, we need to remove it from the multiset (erase by iterator takes a constant time).

    vector<int> advantageCount(vector<int>& A, vector<int>& B) {
        // will automatically sort and keep copies
        multiset<int> s(begin(A), end(A));
        
        for (auto i = 0; i < B.size(); ++i) {
            // if largest of A is smaller at the very beginning, save it for further competition and use smallest of A to fight against B[i]
            // if largest of A is strictly larger, then there might be smaller element in A that is still larger than B[i], so we use upper_bound() to find that
            auto p = ( *s.rbegin() <= B[i] ? s.begin() : s.upper_bound(B[i]) );
            A[i] = *p;
            s.erase(p);
        }
        return A;
    }
};
    // If my fastest horse remained is slower than my opponents' fastest horse,
    // there is no way for me to win, use my slower horse.
    // Otherwise use my fastest horse to win this round.
    // Why using my second fastest horse won't improve my global scores?
    // If my second fastest horse is faster than my opponents' fastest one,
    // it sure is faster than the rest of his horse. Thus proved this strategy is
    // optimal.

// int main() {
//     vector<int> test = {2,4,4,1,1,5,6,10};
//     multiset<int> mlt(begin(test), end(test));
//     cout << *mlt.rbegin() << endl;
//     cout << *std::next(mlt.begin(),3) << endl;
//     for (std::multiset<int>::const_iterator i(mlt.begin()), end(mlt.end());
//             i != end;
//          ++i) std::cout << *i << "\n";
// }




76300