215. Pair Up for Max
A tennis club has 2n players, and each player has a skill number given in nums. The club splits the players into n doubles teams of exactly two players. A team is only as good as its weaker member, so the score of a team is the smaller of its two skill numbers.
Choose how to form the teams so that the total of all team scores is as large as possible, and return that total.
For instance, with skills [2, 9, 4, 5] the teams (2, 4) and (5, 9) score 2 + 5 = 7, while the teams (2, 9) and (4, 5) score 2 + 4 = 6, so the best total is 7.
Example 1
- Input:
- nums = [7,3,9,8,1,5]
- Output:
- 14
- Explanation:
Sorted: 1, 3, 5, 7, 8, 9. Teams (1,3), (5,7), (8,9) score 1 + 5 + 8 = 14.
Example 2
- Input:
- nums = [4,4]
- Output:
- 4
- Explanation:
One team (4, 4) scoring 4.
Example 3
- Input:
- nums = [-3,6,-1,2]
- Output:
- -1
- Explanation:
Sorted: -3, -1, 2, 6. Teams (-3,-1) and (2,6) score -3 + 2 = -1.
Constraints
1 ≤ n ≤ 104, so nums.length = 2n
-104 ≤ nums[i] ≤ 104
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n log n)
- Space
- O(n)