Leetcode 406 Solution

This article provides solution to leetcode question 406 (queue-reconstruction-by-height)

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; } };