Fork me on GitHub

Queue Reconstruction by Height

Posted on

Description

https://leetcode.com/problems/queue-reconstruction-by-height/description/

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
private:
    bool static compare(const pair<int, int>& left, const pair<int, int>& right) {
        return left.second < right.second;
    }
public:
    vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
        sort(people.begin(), people.end(), compare);
        list<pair<int, int>> ret;
        for (auto iter = people.begin(); iter != people.end(); ++iter) {
            auto iterRet = ret.begin();
            int bigger = iter->second;
            while (iterRet != ret.end()) {
                if (iter->first <= iterRet->first) --bigger;
                if (bigger < 0){ret.insert(iterRet, *iter); break;}
                ++iterRet;
            }
            if (iterRet == ret.end()) ret.insert(iterRet, *iter);
        }
        return vector<pair<int, int>>(ret.begin(), ret.end());
    }
};