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

'''
Idea: 对于任意一个nums2[i] 而言，我们应当选择比其大的最小数，若不存在这样的数字，则选择候选集合中的最小值。

My intuition is to use `greedySelect`, a better solution is `greedyTwoPointers`. In essence, they are the same, a clever way in `greedyTwoPointers` is that it sorts index, so no need for `dic` and `traverse again` as in `greedySelect`
'''
from collections import defaultdict, deque


class Solution:
    def advantageCount(self, nums1, nums2):
        def greedySelect(nums1, nums2):
            all = [(num, 1) for num in nums1] # (num, arrNum)
            all += [(num, 2) for num in nums2] # (num, arrNum)
            all.sort(key=lambda pair: pair[0])

            unused = deque([])
            dic = defaultdict(deque) # use deque/list instead of just int is that there may be duplicates in nums2
            j = 0
            while j < len(all):
                # 对于任意一个 nums2[i] 而言，我们应当选择比其大的最小数
                if all[j][1] == 2:
                    i = j + 1
                    found = False
                    while i < len(all):
                        if all[i][1] == 1:
                            dic[all[j][0]].append(all[i][0])
                            all.pop(i)
                            all.pop(j)
                            found = True
                            break
                        else:
                            i += 1
                    # since all is in increasing order, at the point, all[j:] is from nums2
                    if not found:
                        break
                else:
                    unused.append(all[j][0])
                    j += 1

            # traverse again
            ret = []
            for num in nums2:
                if num in dic and len(dic[num]) > 0:
                    ret.append(dic[num][0])
                    dic[num].popleft()
                else:
                    ret.append(unused[0])
                    unused.popleft()
            return ret

        def greedyTwoPointers(nums1, nums2):
            n = len(nums1)
            idx1, idx2 = list(range(n)), list(range(n))
            idx1.sort(key=lambda i: nums1[i])
            idx2.sort(key=lambda i: nums2[i])

            ans = [0] * n
            left, right = 0, n - 1 # pointers for idx2
            for i in range(n): # i for idx1 list
                # 对于任意一个 nums2[i] 而言，我们应当选择比其大的最小数
                if nums1[idx1[i]] > nums2[idx2[left]]:
                    ans[idx2[left]] = nums1[idx1[i]]
                    left += 1
                else:
                    ans[idx2[right]] = nums1[idx1[i]] # sacrifice the small numbers in nums1 to cover big numbers in nums2
                    right -= 1
            return ans

        # return greedySelect(nums1, nums2)
        return greedyTwoPointers(nums1, nums2)
36272