Amazon Online Assessment 2021 (OA) - Class Grouping

The Technical Training Academy, often acronymized as TTA, gives a chance to its existing There are n individuals, each with a unique number that signifies their proficiency in a particular area. An organization wants to group these individuals into sessions where the range of proficiency numbers in any given session is not greater than a specified value, 'maxSpread'. The challenge is to figure out the least number of sessions needed to include all individuals without exceeding the 'maxSpread' in any session.

This question is the same as Group division.

Relevant Amazon OA Problems:

Input

levels: the skill level for each student
max_spread: the maximum allowed skill difference between any two class members of a class

Output

the minimum number of classes that can be formed

Examples

Example 1:

Input:

levels = [1, 4, 7, 3, 4]
max_spread = 2

Output: 3

Explanation:

The trainee must be within maxSpread = 2 levels of each other. In this case, one optimal grouping is {1, 3}, {4, 4}, and {7}. Another possible grouping is {1}, {3, 4, 4}, {7}. There is no way to form fewer than 3 classes.

Constraints

1<=n<=10^5
1<=level[i]<=10^9
0<=maxSpread<=10^9