Minimum Groups

Amazon Prime Video is a subscription video-on-demand over-the-top streaming and rental service. The team at Prime Video is developing a method to divide movies into groups based on the number of awards they have won. A group can consist of any number of movies, but the difference in the number of awards won by any two movies in the group must not exceed k.

The movies can be grouped together irrespective of their initial order. Determine the minimum number of groups that can be formed such that each movie is in exactly one group.

Example

The number of awards per movie are awards = [1, 5, 4, 6, 8, 9, 2], and the maximum allowed difference is k = 3.

One way to divide the movies into the minimum number of group is:

• The first group can contain [2, 1]. The maximum difference between awards of any two movies is 1 which does not exceed k.
• The second group can contain [5, 4, 6]. The maximum difference between awards of any two movies is 2 which does not exceed k.
• The third group can contain [8, 9]. The maximum difference between awards of any two movies is 1 which does not exceed k.

The movies can be divided into a minimum of 3 groups.

Function Description

Complete the function minimumGroups.

minimumGroups has the following parameters:

int awards[n]: the number of awards each movie has earned
int k: the maximum difference in awards counts

Returns

int: the minimum number of groups into which all the movies can be divided.

Constraints

• 1 <= n <= 10^6
• 1 <= k <= 10^4
• 1 <= awards[i] <= 10^9

Sample Case 1

Sample Input For Custom Testing

STDIN    FUNCTION
-----    --------
5     -> awards[] size n = 5
3     -> awards = [3, 1, 4, 3, 9]
1
4
3
9
10    -> k = 10

Sample Output

1

Explanation

The maximum difference between awards of any two movies is 8 so all movies can be in the same group.