Amazon Online Assessment 2021 (OA) - Group division

Here's a simpler way to understand it. Imagine a big school just accepted many students, each of them having different skill levels. The school wants to make sure everyone gets the right amount of attention, so it decides to organize classes according to these skill levels. They have a test which provides each student's skill level, and they use it to know where the student fits. The students' skill levels are displayed in the 'levels' array where levels[i] shows the student i's skill level. However, there's a rule; when you group the students, the highest and lowest skill levels in a group can only be within a certain range, let's call it 'maxSpread', from each other. The big question is - the school needs to figure out the smallest possible number of classes they need to make. This is exactly the problem described in Class Grouping problem.

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 students 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