There are n people that are split into some unknown number of groups. Each person is labeled with a unique ID from 0 to n - 1.
You are given an integer array groupSizes, where groupSizes[i] is the size of the group that person i is in. For example, if groupSizes[1] = 3, then person 1 must be in a group of size 3.
Return a list of groups such that each person i is in a group of size groupSizes[i].
Each person should appear in exactly one group, and every person must be in a group. If there are multiple answers, return any of them. It is guaranteed that there will be at least one valid solution for the given input.
 
Example 1:
Input: groupSizes = [3,3,3,3,3,1,3]
Output: [[5],[0,1,2],[3,4,6]]
Explanation: 
The first group is [5]. The size is 1, and groupSizes[5] = 1.
The second group is [0,1,2]. The size is 3, and groupSizes[0] = groupSizes[1] = groupSizes[2] = 3.
The third group is [3,4,6]. The size is 3, and groupSizes[3] = groupSizes[4] = groupSizes[6] = 3.
Other possible solutions are [[2,1,6],[5],[0,4,3]] and [[5],[0,6,2],[4,3,1]].

Example 2:
Input: groupSizes = [2,1,3,3,3,2]
Output: [[1],[0,5],[2,3,4]]

 
Constraints:

groupSizes.length == n
1 <= n <= 500
1 <= groupSizes[i] <= n

Difficulty: MEDIUM
Tags: Data structures
Skill types: Data structures

Starter code:
class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        

Solutions:
class Solution:

	def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
		groups = defaultdict(list)
		result = []
		for (index, size) in enumerate(groupSizes):
			groups[size].append(index)
			if len(groups[size]) == size:
				result.append(groups.pop(size))
		return result


from collections import defaultdict

class Solution:

	def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
		d = defaultdict(list)
		for i in range(len(groupSizes)):
			d[groupSizes[i]].append(i)
		ans = []
		for i in range(1, max(groupSizes) + 1):
			if i in d:
				for j in range(0, len(d[i]), i):
					ans.append(d[i][j:j + i])
		return ans


class Solution:

	def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
		sizes = {}
		for (i, a) in enumerate(groupSizes):
			if a in sizes:
				sizes[a].append(i)
			else:
				sizes[a] = [i]
		result = []
		for key in sizes.keys():
			if len(sizes[key]) % key == 0:
				result.extend([sizes[key][i * key:(i + 1) * key] for i in range(len(sizes[key]) // key)])
		return result


class Solution:

	def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
		group_sizes_dict = {}
		ret_groups = []
		for i in range(len(groupSizes)):
			if groupSizes[i] not in group_sizes_dict:
				group_sizes_dict[groupSizes[i]] = [i]
			else:
				group_sizes_dict[groupSizes[i]].append(i)
		keys = sorted(group_sizes_dict.keys())
		for i in keys:
			tmp_list = group_sizes_dict[i]
			print(tmp_list)
			to_add = []
			for j in range(len(tmp_list)):
				if (j + 1) % i == 0:
					to_add.append(tmp_list[j])
					ret_groups.append(to_add)
					to_add = []
				else:
					to_add.append(tmp_list[j])
		return ret_groups


class Solution:

	def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
		restrictions = {}
		for unique_id in range(len(groupSizes)):
			group_size = groupSizes[unique_id]
			if group_size in restrictions:
				restrictions[group_size].append(unique_id)
			else:
				restrictions[group_size] = [unique_id]
		res = []
		for group_size in restrictions:
			unique_ids = restrictions[group_size]
			for i in range(0, len(unique_ids), group_size):
				res.append(unique_ids[i:i + group_size])
		return res


class Solution:

	def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
		groups = {}
		for i in range(0, len(groupSizes)):
			if groupSizes[i] in groups:
				groups[groupSizes[i]].append(i)
			else:
				groups[groupSizes[i]] = [i]
		output = []
		for i in groups:
			list1 = []
			for j in groups[i]:
				list1.append(j)
				if len(list1) == i:
					output.append(list1)
					list1 = []
		return output

def main():
	groupSizes = input().split()
	sol = Solution()
	output = sol.groupThePeople(groupSizes)
	print(output)

def __starting_point():
	main()
__starting_point()


class Solution:

	def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
		groups = {}
		output = []
		for i in range(len(groupSizes)):
			belongGroupCount = groupSizes[i]
			existingGroup = groups.get(belongGroupCount)
			if existingGroup is None:
				groups[belongGroupCount] = []
				existingGroup = groups.get(belongGroupCount)
			existingGroup.append(i)
			if len(existingGroup) == belongGroupCount:
				output.append(existingGroup)
				groups[belongGroupCount] = []
			else:
				groups[belongGroupCount] = existingGroup
		return output


class Solution:

	def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
		size_map = {}
		for (idx, group_size) in enumerate(groupSizes):
			if group_size not in size_map:
				size_map[group_size] = [[idx]]
			else:
				for group_list in size_map[group_size]:
					if len(group_list) < group_size:
						group_list.append(idx)
						break
				else:
					size_map[group_size].append([idx])
		ret = []
		for (k, v) in list(size_map.items()):
			ret.extend(v)
		return ret


import collections

class Solution:

	def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
		d = collections.defaultdict(list)
		out = []
		for (i, ele) in enumerate(groupSizes):
			d[ele].append(i)
			print(d)
			if len(d[ele]) == ele:
				out.append(d[ele])
				del d[ele]
		return out


class Solution:

	def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
		smap = {}
		for (i, s) in enumerate(groupSizes):
			if s in smap:
				smap[s].append(i)
			else:
				smap[s] = [i]
		res = []
		for (k, v) in list(smap.items()):
			for i in range(0, len(v), k):
				res.append(v[i:i + k])
				p = i
		return res


class Solution:

	def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
		n = len(groupSizes)
		done = [False for _ in range(n)]
		groups = []
		for i in range(n):
			if done[i]:
				continue
			numInThisGroup = groupSizes[i]
			peopleInThisGroup = []
			for j in range(n):
				if not done[j] and groupSizes[j] == numInThisGroup:
					peopleInThisGroup.append(j)
					if len(peopleInThisGroup) == numInThisGroup:
						break
			groups.append(peopleInThisGroup)
			for person in peopleInThisGroup:
				done[person] = True
		return groups


import numpy as np

class Solution:

	def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
		c = set(groupSizes)
		cn = []
		for i in c:
			newlist = [j for (j, val) in enumerate(groupSizes) if val == i]
			if len(newlist) > i:
				newlist = [newlist[j:j + i] for j in range(0, len(newlist), i)]
				cn.extend(newlist)
			else:
				cn.append(newlist)
		return cn


class Solution:

	def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
		group_dict = dict()
		for i in groupSizes:
			if i in group_dict:
				group_dict[i] += 1
			else:
				group_dict[i] = 1
		for i in group_dict.keys():
			group_dict[i] = int(group_dict[i] / i)
		group_lists = dict()
		for i in group_dict.keys():
			group_lists[i] = [[] for i in range(group_dict[i])]
		for i in range(len(groupSizes)):
			val = groupSizes[i]
			l = group_lists[val]
			j = 0
			while len(l[j]) == val:
				j = j + 1
			l[j].append(i)
		result = []
		for i in group_lists.keys():
			result.extend(group_lists[i])
		return result


class Solution:

	def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
		memory = {}
		for (i, el) in enumerate(groupSizes):
			if el not in memory:
				memory[el] = [[i]]
			else:
				next_available = None
				for j in range(len(memory[el])):
					if len(memory[el][j]) < el:
						next_available = j
				if next_available is None:
					memory[el].append([i])
				else:
					memory[el][next_available].append(i)
		res = []
		for groups in memory.values():
			res.extend(groups)
		return res


class Solution:

	def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
		ret_lst = []
		for iGrpSize in range(len(groupSizes), 0, -1):
			if iGrpSize in groupSizes:
				ppl = []
				for i in range(len(groupSizes)):
					if groupSizes[i] == iGrpSize:
						ppl.append(i)
				if len(ppl) > iGrpSize:
					for i in range(0, len(ppl), iGrpSize):
						ret_lst.append(ppl[i:i + iGrpSize])
				else:
					ret_lst.append(ppl)
		return ret_lst


class Solution:

	def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
		output = []
		subgroup = []
		count = 0
		leng = len(groupSizes)
		subsize = 0
		while count < leng:
			size = min(groupSizes)
			while size in groupSizes:
				ind = groupSizes.index(size)
				subgroup.append(ind)
				groupSizes[ind] = 501
				count += 1
				subsize += 1
				if subsize % size == 0:
					output.append(subgroup)
					subgroup = []
					subsize = 0
			subgroup = []
		return output


class Solution:

	def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
		res = []
		d = collections.defaultdict(list)
		for i in range(len(groupSizes)):
			d[groupSizes[i]].append(i)
			if len(d[groupSizes[i]]) == groupSizes[i]:
				res.append(d[groupSizes[i]])
				d[groupSizes[i]] = []
		return res


class Solution:

	def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
		dic = {}
		res = []
		for i in range(len(groupSizes)):
			if groupSizes[i] == 1:
				res.append([i])
				continue
			if groupSizes[i] in dic:
				dic[groupSizes[i]].append(i)
			else:
				dic[groupSizes[i]] = [i]
			if len(dic[groupSizes[i]]) == groupSizes[i]:
				res.append(dic[groupSizes[i]])
				dic[groupSizes[i]] = []
		return res


class Solution:

	def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
		d = dict(enumerate(groupSizes))
		d = {k: v for (k, v) in sorted(list(d.items()), key=lambda item: item[1])}
		a = []
		b = []
		tmp = next(iter(list(d.values())))
		for (k, v) in list(d.items()):
			if tmp == v and len(a) < v:
				a += [k]
			else:
				b.append(a)
				a = []
				a += [k]
			if k == list(d.keys())[-1]:
				b.append(a)
			tmp = v
		return b


class Solution:

	def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
		groups = []
		sizes = {}
		for i in range(len(groupSizes)):
			if groupSizes[i] not in sizes:
				sizes[groupSizes[i]] = [i]
			else:
				sizes[groupSizes[i]].append(i)
		for (size, group) in list(sizes.items()):
			for i in range(0, len(group), size):
				groups.append(group[i:i + size])
		return groups


class Solution:

	def groupThePeople(self, gr: List[int]) -> List[List[int]]:
		res = []
		for i in range(len(gr)):
			count = gr[i]
			if count != 0:
				temp = []
				for j in range(len(gr)):
					for k in range(count):
						if gr[j] == count:
							temp.append(j)
							gr[j] = 0
						if len(temp) == count:
							res.append(temp)
							temp = []
				if len(temp) != 0:
					res.append(temp)
		return res


class Solution:

	def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
		l = len(groupSizes)
		key = {}
		ans = []
		for i in range(l):
			now = groupSizes[i]
			if now not in key.keys():
				key[now] = []
				key[now].append(i)
			elif len(key[now]) != now:
				key[now].append(i)
			else:
				ans.append(key[now])
				key[now] = []
				key[now].append(i)
		for i in key.keys():
			if key[i] not in ans:
				ans.append(key[i])
				continue
		return ans


class Solution:

	def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
		res = []
		dic = {}
		for (idx, size) in enumerate(groupSizes):
			if size == 1:
				res.append([idx])
			elif size > 1:
				if size not in dic:
					dic[size] = [idx]
				else:
					dic[size].append(idx)
					if len(dic[size]) == size:
						res.append(dic[size])
						del dic[size]
		return res


class Solution:

	def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
		groups = {}
		for (id, size) in enumerate(groupSizes):
			if size not in groups:
				groups[size] = [[id]]
			else:
				lastGroup = groups[size][-1]
				if len(lastGroup) != size:
					groups[size][-1] += [id]
				else:
					groups[size] += [[id]]
		flatList = []
		for (k, v) in list(groups.items()):
			flatList += v
		return flatList


class Solution:

	def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
		groups = []
		cache = {}
		for i in range(len(groupSizes)):
			if groupSizes[i] not in cache:
				cache[groupSizes[i]] = []
			if len(cache[groupSizes[i]]) < groupSizes[i]:
				cache[groupSizes[i]].append(i)
			if len(cache[groupSizes[i]]) == groupSizes[i]:
				groups.append(cache[groupSizes[i]])
				cache.pop(groupSizes[i])
		return groups


class Solution:

	def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
		d = {}
		res = []
		for i in range(len(groupSizes)):
			d[groupSizes[i]] = d.setdefault(groupSizes[i], []) + [i]
		for (x, y) in d.items():
			for j in range(0, len(y), x):
				res.append(y[j:j + x])
		return res


class Solution:

	def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
		groups = sorted(list(enumerate(groupSizes)), key=lambda x: x[1])
		out = []
		while groups:
			last_group_idx = -groups[-1][1]
			out.append([t[0] for t in groups[last_group_idx:]])
			groups = groups[:last_group_idx]
		return out


from collections import defaultdict

class Solution:

	def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
		all_groups = list()
		assignments = defaultdict(list)
		for (i, size) in enumerate(groupSizes):
			assignments[size].append(i)
		return [people[i:i + size] for (size, people) in list(assignments.items()) for i in range(0, len(people), size)]