Approach 1: Greedy
If the smallest card
A beats the smallest card
B, we should pair them. Otherwise,
a is useless for our score, as it can't beat any cards.
Why should we pair
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.
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
sortedA, we will either have
a beat that card
assigned[b]), or throw
a out (put
Afterwards, we can use our annotations
remaining to reconstruct the answer. Please see the comments for more details.
Time Complexity: , where is the length of
Space Complexity: .
Analysis written by: @awice.