Problem

Let’s consider the following situation. You’ve invited a lot of children to a celebration party, and you want to entertain them and also teach them something in the process. You are going to hire a few teachers and divide the children into groups and assign a teacher to each of the groups. This teacher will work with this group through the whole party.

But you know that for a teacher to work with a group of children efficiently children of that group should be of relatively the same age. More specifically age of any two children in the same group should differ by at most, one year.

Also, you want to minimize the number of groups. Because you want to hire fewer teachers, and spend the money on presents and other kinds of entertainment for the children. So, you need to divide children into the minimum possible number of groups. Such that the age of any two children in any group differs by at most one year.

Examples

Example 1

1
2
3
4
5
6
7
8

Input: ages = [2.5, 3.2, 3.5, 4.0, 4.8, 5.2, 6.0]
Output: 3
 Explanation:
 - Group 1: [2.5, 3.2, 3.5]
 - Group 2: [4.0, 4.8, 5.2]
 - Group 3: [6.0]
 
 Minimum number of groups = 3

Example 2

1
2
3
4
5
6
7
8
9

Input: [1.1, 2.1, 3.3, 3.9, 5.0, 6.5]
Output: 4
Explanation:
- Group 1: [1.1, 2.1]
- Group 2: [3.3, 3.9]
- Group 3: [5.0]
- Group 4: [6.5]

Minimum number of groups = 4

Solution

Method 1 - Greedy

Reasoning

  • Sorting ensures we consider ages in increasing order, preventing unnecessary splitting.
  • By tracking the maximum group range (currentMax + 1.0), we minimise the number of groups required.
  • If an age exceeds the range of the current group, start a new group.

Approach

  1. Sort the Input: Sorting ensures that we attempt to group consecutive elements together.
  2. Maintain a Group’s Upper Bound: Use a variable to track the maximum allowable age for the current group. If the next age exceeds this, start a new group.
  3. Increment Group Counter: Every time a new group is started, increment the group counter.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    int minGroups(vector<double>& ages) {
        sort(ages.begin(), ages.end()); // Step 1: Sort ages
        int groups = 1; // Start with 1 group
        double currentMax = ages[0]; // First group's maximum age

        for (double age : ages) {
            if (age > currentMax + 1.0) { // Step 2: Check if new group needed
                groups++;
                currentMax = age; // Start new group with this age
            }
        }
        return groups;
    }
};

int main() {
    Solution solution;
    vector<double> ages = {2.5, 3.2, 3.5, 4.0, 4.8, 5.2, 6.0};
    cout << solution.minGroups(ages) << endl; // Output: 3
    return 0;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

func minGroups(ages []float64) int {
	sort.Float64s(ages) // Step 1: Sort ages
	groups := 1
	currentMax := ages[0] // First group's maximum age

	for _, age := range ages {
		if age > currentMax+1.0 { // Step 2: Check if new group needed
			groups++
			currentMax = age
		}
	}
	return groups
}

func main() {
	ages := []float64{2.5, 3.2, 3.5, 4.0, 4.8, 5.2, 6.0}
	fmt.Println(minGroups(ages)) // Output: 3
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public int minGroups(double[] ages) {
        Arrays.sort(ages); // Step 1: Sort ages
        int groups = 1;
        double currentMax = ages[0]; // First group's maximum age

        for (double age : ages) {
            if (age > currentMax + 1.0) { // Step 2: Check if new group needed
                groups++;
                currentMax = age;
            }
        }
        return groups;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        double[] ages = {2.5, 3.2, 3.5, 4.0, 4.8, 5.2, 6.0};
        System.out.println(solution.minGroups(ages)); // Output: 3
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    fun minGroups(ages: DoubleArray): Int {
        ages.sort() // Step 1: Sort ages
        var groups = 1
        var currentMax = ages[0] // First group's maximum age

        for (age in ages) {
            if (age > currentMax + 1.0) { // Step 2: Check if new group needed
                groups++
                currentMax = age
            }
        }
        return groups
    }
}

fun main() {
    val solution = Solution()
    val ages = doubleArrayOf(2.5, 3.2, 3.5, 4.0, 4.8, 5.2, 6.0)
    println(solution.minGroups(ages)) // Output: 3
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def minGroups(self, ages):
        ages.sort()  # Step 1: Sort ages
        groups = 1
        current_max = ages[0]  # First group's maximum age

        for age in ages:
            if age > current_max + 1.0:  # Step 2: Check if new group needed
                groups += 1
                current_max = age

        return groups


# Example usage
solution = Solution()
ages = [2.5, 3.2, 3.5, 4.0, 4.8, 5.2, 6.0]
print(solution.minGroups(ages))  # Output: 3
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

fn min_groups(mut ages: Vec<f64>) -> i32 {
    ages.sort_by(|a, b| a.partial_cmp(b).unwrap()); // Step 1: Sort ages
    let mut groups = 1;
    let mut current_max = ages[0]; // First group's maximum age

    for &age in &ages {
        if age > current_max + 1.0 { // Step 2: Check if new group needed
            groups += 1;
            current_max = age;
        }
    }
    groups
}

fn main() {
    let ages = vec![2.5, 3.2, 3.5, 4.0, 4.8, 5.2, 6.0];
    println!("{}", min_groups(ages)); // Output: 3
}

Complexity

  • ⏰ Time complexity: O(n log n)
    • Sorting: O(n * log(n))
    • Iteration: O(n)
    • Total complexity: O(n * log(n)).
  • 🧺 Space complexity: O(1) as sorting can be done in place