class Solution1(object):
    def advantageCount(self, A, B):
        """
        方法1
        对于B中的每一个元素，在A中找出第一个比他大的元素
        超时
        58 / 67 test cases passed.
        """
        result = [-1]*len(A)
        A.sort()
        for i in range(len(B)):
            for j in range(len(A)):
                if A[j] > B[i]:
                    result[i] = A[j]
                    A[j] = A[j]*(-1)-1
                    break


        index = 0
        for i in range(len(result)):
            if result[i] == -1:
                while(index < len(A) and A[index] < 0):
                    index += 1
                if index == len(A):
                    break
                result[i] = A[index]
                index += 1
        return result

class Solution(object):
    """
    分别将A B进行降序排序，然后每次取A最大的取匹配B最大的，如果搞不定，就取A最小的补上，这样A可以保留较大的元素来与B抗衡
    这里注意要记录B中元素原来的位置，用个二元组
    """
    def advantageCount(self, A, B):
        A.sort(reverse=True)
        B =[[ele,idx] for idx,ele in enumerate(B)]
        B.sort(reverse=True)
        result = [-1]*len(A)
        left, right = 0, len(A)-1
        for i in range(len(result)):
            if A[left] > B[i][0]:
                result[B[i][1]] = A[left]
                left += 1
            else:
                result[B[i][1]] = A[right]
                right -= 1
        return result