Most Rounds Won in the Duel
MediumGreedy
Problem
Two teams play a series of one-on-one rounds. The opponents have already fixed their line-up: theirs[i] is the strength of the opponent in round i. You may arrange your players ours in any order; in each round the strictly stronger player wins (ties are losses for you).
Return the largest number of rounds you can win.
Example 1
- Input:
- ours = [5, 1, 9, 3], theirs = [4, 8, 2, 6]
- Output:
- 3
Play 3 against 2, 5 against 4, 9 against 6, and sacrifice 1 against 8.
Example 2
- Input:
- ours = [3, 3, 3], theirs = [3, 3, 3]
- Output:
- 0
Ties never count as wins.
Constraints
- 1 ≤ ours.length = theirs.length ≤ 10^5
- 0 ≤ ours[i], theirs[i] ≤ 10^9
Hint
Show the first hint
Which opponent is the easiest to beat, and which of your players should you spend on them?
Walkthrough
How to approach it
01Clarify before coding
- Do we need the arrangement? No, only the number of wins.
- Do ties count? No, a win must be strictly greater.
- Can strengths repeat? Yes, on both sides.
02Brute force
Try every permutation of our players and count the wins.
Cost: O(n! · n): impossible beyond a dozen players.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.