Pair Up the Players
EasyGreedy
Problem
A club has an even number of players with skill ratings ratings. They must be split into pairs, and each pair is scored by its weaker member's rating.
Return the largest possible sum of pair scores.
Example 1
- Input:
- ratings = [1, 4, 3, 2]
- Output:
- 4
Pairs (1, 2) and (3, 4) score 1 + 3 = 4, the best possible.
Example 2
- Input:
- ratings = [6, 2, 6, 5, 1, 2]
- Output:
- 9
Sorted: 1, 2, 2, 5, 6, 6. Pairs (1, 2), (2, 5), (6, 6) score 1 + 2 + 6.
Constraints
- 2 ≤ ratings.length ≤ 2 · 10^4, even
- -10^4 ≤ ratings[i] ≤ 10^4
Hint
Show the first hint
The very weakest player scores for their pair no matter who they are matched with. Who should be their partner?
Walkthrough
How to approach it
01Clarify before coding
- Is the number of players always even? Yes.
- Can ratings be negative? Yes, down to -10^4.
- Do we need the pairs? No, only the sum.
02Brute force
Enumerate every perfect pairing and keep the best sum of minima.
Cost: (2n − 1)!! pairings, about 10^4 already for 10 players: exponential.
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.