587. Head-to-Head Wins
Two table-tennis clubs each field n players. Your club's players have skill ratings mine[i], and the rival club has already fixed its line-up: its player at table i has rating theirs[i]. Before play starts you may seat your players at the tables in any order you like, but every table gets exactly one of your players and one rival player.
At each table the player with the strictly higher rating wins; a tie counts as a win for nobody. Return the largest number of tables your club can win with the best possible seating. The intended solution runs in O(n log n) time and O(1) extra space beyond sorting.
Example 1
- Input:
- mine = [5,9,2,7], theirs = [6,3,8,4]
- Output:
- 3
- Explanation:
Seat 5 against 3, 7 against 4 and 9 against 6 for three wins, while the rating-2 player is sacrificed against 8.
Example 2
- Input:
- mine = [1,1,1], theirs = [1,1,1]
- Output:
- 0
- Explanation:
Every match is a tie, so nobody wins any table.
Example 3
- Input:
- mine = [4,4,8], theirs = [4,7,3]
- Output:
- 2
- Explanation:
The rating-4 players can beat the 3, and the 8 beats a 4 or a 7, giving two wins; a tie at 4 against 4 does not count.
Constraints
- 1 ≤ n ≤ 105, where n = mine.length = theirs.length
- -109 ≤ mine[i], theirs[i] ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(1) extra (after in-place sorting)