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:
- Shipment Imbalance
- Simple Cipher
- Decode String Frequency
- Grid Connections
- Counting Binary substrings
Input
levels: the skill level for each studentmax_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^51<=level[i]<=10^90<=maxSpread<=10^9