Greedy Algorithm to Group the Numbers/Items Given the Group Size They Belong To

There are n people whose IDs go from 0 to n – 1 and each person belongs exactly to one group. Given the array groupSizes of length n telling the group size each person belongs to, return the groups there are and the people’s IDs each group includes. You can return any solution in any order and the same applies for IDs. Also, it is guaranteed that there exists at least one solution.

Example 1:
Input: groupSizes = [3,3,3,3,3,1,3]
Output: [[5],[0,1,2],[3,4,6]]
Explanation:
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 &lt= 500
1 <= groupSizes[i] <= n

Hints:
Put people’s IDs with same groupSize into buckets, then split each bucket into groups.
Greedy fill until you need a new group.

Group the Numbers by Greedy Algorithm

We can put the items in the same bucket, then apply a Greedy Algorithm to fill the groups (from large to small) until I need a new group. In C++, the std::map maintains the keys sorted in ascending order. We then can start from the last iterator (which is one position less than the end iterator), fill the groups (using the items in the buckets from largest to smallest order), until all elements are arranged.

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

class Solution {
public:
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        vector<vector<int>> ans;
        map<int, vector<int>> ids;
        for (int i = 0; i < groupSizes.size(); ++ i) {
            ids[groupSizes[i]].push_back(i);
        }
        int K = groupSizes.size();
        for (auto it = --ids.end(); K > 0; --K) {
            if (ans.empty() || (ans.back().size() >= it->first)) {
                ans.push_back({}); // need a new group
            }
            ans.back().push_back(it->second.back());
            it->second.pop_back(); // remove the ID from the candidate list
            if (it->second.empty()) {
                -- it; // next largest bucket
            }
        }
        return ans;
    }
};

class Solution {
public:
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        vector<vector<int>> ans;
        map<int, vector<int>> ids;
        for (int i = 0; i < groupSizes.size(); ++ i) {
            ids[groupSizes[i]].push_back(i);
        }
        int K = groupSizes.size();
        for (auto it = --ids.end(); K > 0; --K) {
            if (ans.empty() || (ans.back().size() >= it->first)) {
                ans.push_back({}); // need a new group
            }
            ans.back().push_back(it->second.back());
            it->second.pop_back(); // remove the ID from the candidate list
            if (it->second.empty()) {
                -- it; // next largest bucket
            }
        }
        return ans;
    }
};

Alternatively, we can iterate the map using the rbegin() and rend() which reverses the order (from right to left).

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

class Solution {
public:
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        vector<vector<int>> ans;
        map<int, vector<int>> ids;
        for (int i = 0; i < groupSizes.size(); ++ i) {
            ids[groupSizes[i]].push_back(i);
        }
        for (auto it = rbegin(ids); it != ids.rend(); ) {
            if (ans.empty() || (ans.back().size() >= it->first)) {
                ans.push_back({}); // need a new group
            }
            ans.back().push_back(it->second.back());
            it->second.pop_back();  // remove the ID from the candidate list
            if (it->second.empty()) {
                ++ it;
            }
        }
        return ans;
    }
};

class Solution {
public:
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        vector<vector<int>> ans;
        map<int, vector<int>> ids;
        for (int i = 0; i < groupSizes.size(); ++ i) {
            ids[groupSizes[i]].push_back(i);
        }
        for (auto it = rbegin(ids); it != ids.rend(); ) {
            if (ans.empty() || (ans.back().size() >= it->first)) {
                ans.push_back({}); // need a new group
            }
            ans.back().push_back(it->second.back());
            it->second.pop_back();  // remove the ID from the candidate list
            if (it->second.empty()) {
                ++ it;
            }
        }
        return ans;
    }
};

Both implementations require O(N) linear space and the time complexity is also O(N) where N is the number of the elements in the original list i.e. each number will be visited exactly twice.

–EOF (The Ultimate Computing & Technology Blog) —