Group the People Given the Group Size They Belong To

Problem Id: 1282 Difficulty: Medium Tag: Greedy


Intuition

This problem is marked as level Medium. But it is still simple.

The only requirement of the description is that the people with the same group size should be put together into one or more groups with size GroupSize.

So we could use greedy to solve this problem.

Solution


from collections import defaultdict


class Solution:
    def groupThePeople(self, groupSizes):
        cache = defaultdict(list)
        ans = []
        for i, group_size in enumerate(groupSizes):
            cache[group_size].append(i)
            if len(cache[group_size]) == group_size:
                ans.append(cache[group_size])
                cache[group_size] = []
        return ans