<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>

// Author : Ali Eren Çiftçi
// Question Link : https://leetcode.com/problems/advantage-shuffle/

/*
    Problem Statement:
        You are given two integer arrays nums1 and nums2 both of the same length.
        The advantage of nums1 with respect to nums2 is the number of indices i for which nums1[i] > nums2[i].
        Return any permutation of nums1 that maximizes its advantage with respect to nums2.

    Solution:
    The main thing we need to avoid is having every element in nums1 be greater than the corresponding element in nums2.
    Therefore, for each element \U0001d465 in nums2, we need to find the smallest element in nums1 that is greater than
    \U0001d465 and assign it to the position of \U0001d465

    To do this as effectively as possible, we should start with the smallest elements in nums2.

    We should store the elements from nums1 that cannot be assigned to nums2 (because they are too small) in a vector called remaining.
    Then, we assign these remaining elements to the positions in nums2 where we couldn't find a suitable larger element.

    ex:
        nums1 = [2,7,11,15], nums2 = [3,10,4,11]
        n2:          n1:
        3,  0       2,  0  In the first step, since the element in n1 is not larger than the element in n2, we assign it to the remaining vector
        4,  2       7,  1  in the second step, since 7 > 3, make nums1[0] = 7 (index of 3 is 0)
        10, 1       11, 2  since 11 > 4 in the third step, nums[2] = 11
        11, 3       15, 3  since 15 > 10 in the fourth step, nums[1] = 15

        We've finished every element in the n1 heap, now it's time to place the rest.
        n2 had {11,3} and remaining had {2,0} so nums1[3] = 2; In the end, the following situation occurred.
        nums1 = [7,15,11,2]
        nums2 = [3,10,4,11]

    TC => O(NlogN)
    SC => O(N)
*/
class Solution {
public:
    /*
    vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {

        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> n1, n2;

        for(int i = 0; i < nums1.size(); ++i) //Let's sort the values from smallest to largest, keeping the indexes
        {
            n1.push({nums1[i],i});
            n2.push({nums2[i],i});
        }

        vector<pair<int,int>> kalan;

        while(!n2.empty()) // until we find the corresponding element for every element in n2
        {
            if(n1.empty()){ // If the elements in n1 are finished, look at the remaining vector
                nums1[n2.top().second] = kalan.back().first;
                n2.pop();
                kalan.pop_back();
            }
            else{
                if(n1.top().first > n2.top().first){ // If we've found the corresponding element of n2's smallest element.
                    nums1[n2.top().second] = n1.top().first;
                    n2.pop();
                    n1.pop();
                } else { // If the smallest element of n1 does not satisfy the requirement, keep it and move on to the next one
                    kalan.push_back(n1.top());
                    n1.pop();
                }
            }
        }
        return nums1;
    }*/
    vector<int> advantageCount(vector<int> &nums1, vector<int> &nums2){
    int n = nums2.size();
	vector<bool> used(n, false);
	vector<int> ans(n);
	priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq1, pq2;
	
	for (int i = 0; i < n; i++) {
		pq1.push({nums1[i], i});
pq2.push({nums2[i], i});
}

while (!pq1.empty()) {
pair<int,int> element2 = pq2.top();
pq2.pop();
pair<int,int> element1 = pq1.top();
pq1.pop();
while (element1.first <= element2.first && !pq1.empty()) {
	element1 = pq1.top();
	pq1.pop();
} 
if (element1.first > element2.first) {
	ans[element2.second] = element1.first;
	used[element1.second] = true;
}
else {
	ans[element2.second] = element1.first;
	used[element1.second] = true;
}
}
for (int i = 0; i < n; i++) {
	if (!used[i]) {
	pair<int,int> element2 = pq2.top();
	ans[element2.second] = nums1[i];
	pq2.pop();
}
}
	return ans;
}

};
71300