Group the People Given the Group Size They Belong To

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]]

Approach

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class GroupSize {
    public static void main(String[] args) {
        int[] groupSizes = { 3, 3, 3, 3, 3, 1, 3 };
        List<List<Integer>> group = groupThePeople(groupSizes);
        System.out.println(Arrays.asList(group));
    }

    // function to group the peoples
    static List<List<Integer>> groupThePeople(int[] groupSizes) {
        List<int[]> v = new ArrayList<int[]>();
        for (int i = 0; i < groupSizes.length; i++)
            v.add(new int[] { groupSizes[i], i });

        // sort the vector pair array
        Collections.sort(v, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });

        List<List<Integer>> res = new ArrayList<List<Integer>>();
        int i = 0;
        int n = v.size();

        // iterate till the length of array
        while (i < n) {
            List<Integer> x = new ArrayList<Integer>();
            int p = v.get(i)[0] - 1;
            while (i + 1 < n && v.get(i)[0] == v.get(i + 1)[0] && p > 0) {
                x.add(v.get(i)[1]);
                i++;
                p--;

            }
            x.add(v.get(i)[1]);
            i++;
            res.add(x);
        }
        return res;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

//function to group the peoples
vector<vector<int>> groupThePeople(vector<int>& groupSizes) 
{
        vector<pair<int,int>> v;
        for(int i=0;i<groupSizes.size();i++)
               v.push_back({groupSizes[i],i});

      //sort the vector pair array
       sort(v.begin(),v.end());
       vector<vector<int>> res;
       int i=0;
       int n=v.size();

        //iterate till the length of array
        while(i<n)
         {
            vector<int>x;
            int p=v[i].first-1;
            while(i+1<n&&v[i].first==v[i+1].first&&p>0) 
            {
                x.push_back(v[i].second);
                i++;
                p--;
                
            }
            x.push_back(v[i].second);
            i++;
            res.push_back(x);
         }
        return res;
}
int main()
{
    vector<int > groupSizes ={3,3,3,3,3,1,3};
    vector<vector<int>> group=groupThePeople(groupSizes);
    cout<<"[";
    for(int i=0;i<group.size();i++)
      {
          cout<<"[";
          for(int j=0;j<group[i].size();j++)
            {
                cout<<group[i][j];
                if(j!=group[i].size()-1)
                   cout<<",";
            }
            cout<<"]";
            if(i!=group.size()-1)
              cout<<",";
      }
     cout<<"]";
     return 0;
}