Pair Coders by Rating
Updated
Problem statement
You are given an integer array ratings, where ratings[i] is the rating of the i-th coder. You want to split all the coders into teams of exactly two, so that every coder is in exactly one team.
The gap of a team is the absolute difference between the ratings of its two coders. Return the smallest possible sum of the gaps over all teams.
If the number of coders is odd, one coder is always left without a partner. In that case, return -1.
Function
minTotalRatingGap(ratings: int[]) → intExamples
Example 1
ratings = [5,1,4,8]return = 6In sorted order the ratings are 1, 4, 5, 8. Pairing (1, 4) and (5, 8) gives gaps 3 + 3 = 6. The other two ways cost more: (1, 5) and (4, 8) give 4 + 4 = 8, and (1, 8) and (4, 5) give 7 + 1 = 8. So the answer is 6, even though the closest two ratings, 4 and 5, end up in different pairs.
Example 2
ratings = [7,3,9]return = -1There are 3 coders. With an odd number of coders, one coder is always left without a partner, so the answer is -1.
Example 3
ratings = [10,2,10,2]return = 0Pair the two coders rated 2 with each other and the two coders rated 10 with each other. Both gaps are 0, so the answer is 0.
Constraints
1 <= ratings.length <= 10^50 <= ratings[i] <= 10^9