Optimal Team Formation

Easy

0/40

0 upvote

Problem statement

A coach is forming a new team of size K from a pool of N available players. Each player has a skill rating, given as an integer. The coach wants to form the most cohesive team possible.

Team Cohesion is defined as the difference between the highest and lowest skill ratings of the players on the team. A smaller difference indicates better cohesion.

Your task is to find the minimum possible cohesion score for a team of size K. To do this, you will need to find a group of K players from the pool whose maximum and minimum skill ratings are as close as possible.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains two space-separated integers, N (the total number of players) and K (the required team size).

The second line contains N space-separated integers, representing the skill ratings of the players.

Output Format:

Your function should return a single integer representing the minimum possible cohesion score.

Note:

The most efficient way to solve this is to first sort the player ratings. Once sorted, the most cohesive teams of size K will always be a contiguous block of K players. You can then slide a window of size K across the sorted array to find the block with the minimum difference between its start and end.

Sample Input 1:

8 4
3 4 1 9 56 7 9 12

Sample Output 1:

Explanation for Sample 1:

First, sort the player ratings: [1, 3, 4, 7, 9, 9, 12, 56].
Now, check all possible teams of size K=4 by sliding a window:
  Team [1, 3, 4, 7]: Cohesion = 7 - 1 = 6.
  Team [3, 4, 7, 9]: Cohesion = 9 - 3 = 6.
  Team [4, 7, 9, 9]: Cohesion = 9 - 4 = 5.
  Team [7, 9, 9, 12]: Cohesion = 12 - 7 = 5.
  Team [9, 9, 12, 56]: Cohesion = 56 - 9 = 47.
The minimum cohesion found is 5.

Sample Input 2:

7 3
10 20 12 15 17 30 11

Sample Output 2:

Expected Time Complexity:

The expected time complexity is O(N log N).

Constraints:

1 <= K <= N <= 10^5
1 <= Skill Rating <= 10^9

Time limit: 1 sec

Approaches (1)

Approach 1

Time Complexity

Space Complexity

(100% EXP penalty)

Optimal Team Formation

Console