Teams by Skill
Medium · greedy
A coach has a list of players, where skills[i] is the skill rating of player i. The coach wants to split every player into teams. A team may have any number of players, including just one, and each player belongs to exactly one team.
A team is balanced if its highest rating and its lowest rating differ by at most d.
Return the smallest number of teams needed so that every team is balanced.
Two players can have the same rating, and the order of skills does not matter.
Examples
Example 1
Input: skills = [7, 2, 9, 4, 5], d = 2
Output: 3
One way is {2, 4}, {5, 7} and {9}. Every team has a spread of at most 2, and two teams are not enough.
Example 2
Input: skills = [10, 10, 10], d = 0
Output: 1
Equal ratings differ by 0, so everyone fits in one team.
Example 3
Input: skills = [1, 10, 20], d = 5
Output: 3
Every pair differs by more than 5, so each player needs their own team.
Constraints
- 1 <= len(skills) <= 10^5
- 0 <= skills[i] <= 10^9
- 0 <= d <= 10^9