Leetcode 406 Solution
This article provides solution to leetcode question 406 (queue-reconstruction-by-height)
Access this page by simply typing in "lcs 406" in your browser address bar if you have bunnylol configured.
Leetcode Question Link
https://leetcode.com/problems/queue-reconstruction-by-height
Solution
class Solution {
public:
vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
vector<pair<int, int>> res;
vector<pair<int, int>> a(people.begin(), people.end());
vector<bool> b(people.size());
while (res.size() < people.size())
{
int low_pos = -1;
for (int i = 0; i < a.size(); i++)
{
if (b[i])
continue;
if (low_pos == -1 && a[i].second == 0)
low_pos = i;
else if (a[low_pos].first > a[i].first && a[i].second == 0)
low_pos = i;
}
b[low_pos] = true;
res.push_back(people[low_pos]);
for (int i = 0; i < a.size(); i++)
{
if (b[i] == true)
continue;
if (a[low_pos].first >= a[i].first)
a[i].second--;
}
}
return res;
}
};