Solution
Approach 1: Greedy
Intuition
If the smallest card a
in A
beats the smallest card b
in B
, we should pair them. Otherwise, a
is useless for our score, as it can't beat any cards.
Why should we pair a
and b
if a > b
? Because every card in A
is larger than b
, any card we place in front of b
will score a point. We might as well use the weakest card to pair with b
as it makes the rest of the cards in A
strictly larger, and thus have more potential to score points.
Algorithm
We can use the above intuition to create a greedy approach. The current smallest card to beat in B
will always be b = sortedB[j]
. For each card a
in sortedA
, we will either have a
beat that card b
(put a
into assigned[b]
), or throw a
out (put a
into remaining
).
Afterwards, we can use our annotations assigned
and remaining
to reconstruct the answer. Please see the comments for more details.
Complexity Analysis

Time Complexity: , where is the length of
A
andB
. 
Space Complexity: .
Analysis written by: @awice.