Leetcode 406 Solution

This article provides solution to leetcode question 406 (queue-reconstruction-by-height).
Categories:
Tags:
Access this page by simply typing in "lcs 406" in your browser address bar if you have bunnylol configured.

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