```
class Solution {
public:
vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
multimap<int, int> mmap; // To keep the people sorted wrt their height
vector<pair<int, int>> res(people.size(), make_pair(-1, -1)); // return value
for (auto it = people.begin(); it != people.end(); it++) {
mmap.insert(*it);
}
for (auto it = mmap.begin(); it != mmap.end(); it++) {
int key = it->first;
int val = it->second;
int i = 0, j = 0;
while (j <= val) {
// this person should have val number of people
// ahead whose height are more than or equal to
// this person's height. But if there is a person
// whose height is smaller than this person's height,
// skip incrementing the j.
if (res[i].first == -1 || res[i].first >= key) j++;
i++;
}
res[--i] = make_pair(key, val); // Found the place to insert this person
}
return res;
}
};
```