418. Social Network Problem

Given:

There are N people in a social network and there are friends group. Each person can be part of a friend group of a specific size.

Number of people in the social network - N

An array of size N specifying group size for each person. - (g0, g2, g3,....., gn). The first person (at index 0) is part of a friend group of maximum size g0, the second person(at index 1) is part of a friend group of maximum size g2 and so on.       

Objective: Write an algorithm to create the minimum number of friend groups so that each person can be put into one of these groups as per the given group size of each person. 

Output: Print minimum no of groups and persons assigned to each group.

Example:

N = 7
people = {3, 3, 3, 3, 3, 1, 3}
Person 0 is being part of a group of maximum size 3, person 1 is be to part of a group of maximum size 3 ..., person 5 is be to part of a group of maximum size 1.
Output:
5
0 1 2
3 4 6
************
N = 2
people = {3, 2}
Person 0 is being part of a group of maximum size 3, person 1 is be to part of a group of maximum size 2
Output:
0 1
Note: person 0 can be part of maximum group size 3, So this person can be part of a group size 2 where person 1 belongs. So minimum no of groups required are 1 in which both person 0 and person 1 can be together.
************
N = 9
people = {3, 2, 3, 3, 2, 2, 3, 2, 6};
Output:
1 4
5 7
0 2 3
6 8

Approach: 

1. Iterate through given array.
2. Create a Map for each group size present, with group size as key and person's index as the value in the map.
3. Now start forming the group, Iterate through map, lowest key first (will start forming smallest group first since person who has to be part of a smaller group, cannot be part of a bigger group if needed and vice versa is true) and start putting persons in a group size (same as key). for ease create TreeMap which will have keys in sorted order.
4. Pull the person from higher group size to lower If needed to complete the group.
5. See the walkthrough of the example below for more understanding.

N = 7
groups = {3, 3, 1, 3, 2, 3}
Tree Map:
key(Group Size)	values(Persons)
1 			2
2			4
3 			0 1 3 5
First group: size 1, person 2
Second group: size 2, person- 4,  (put person 0 in this group as well to complete the group, this way the total number of groups can be minimized)
Third group: size 3, person: 1 3
Result
Group size: 1, Persons:
Group size: 2, Persons: 4
Group size: 3, Persons: 1 3

Output:

Group size: 1, Persons: 2
Group size: 2, Persons: 4 0
Group size: 3, Persons: 1 3 5
______________________________________________
Group size: 2, Persons: 1 4
Group size: 2, Persons: 5 7
Group size: 3, Persons: 0 2 3
Group size: 3, Persons: 6 8