# Amazon Online Assessment 2021 (OA) - Class Grouping

Amazon Technical Academy (ATA) provides in-demand, technical training to current Amazon employees looking to broaden their skill sets. ATA has admitted a group of n prospective trainees with varying skill levels. To better accommodate the trainees, ATA has decided to create classes tailored to the skill levels. A placement examination will return a skill level that will be used to group the trainees into classes, where levels[i] represents the skill level of trainee i. All trainees within a class must have a skill level within maxSpread, a specified range of one another. Determine the minimum number of classes that must be formed.

This problem is 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:

``````1levels = [1, 4, 7, 3, 4]
2max_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`

## Title

### Script

Lorem Ipsum is simply dummy text of the printing and typesetting industry. `Lorem` `Ipsum` has been the industry's standard dummy text ever since the 1500s, when an unknown printer took a galley of type and scrambled it to make a type specimen book.

Contrary to popular belief, `Lorem` `Ipsum` is not simply random text.

``````1  >>> a = [1, 2, 3]
2  >>> a[-1]
3  3``````

Get premium for instant access to all content and solutions