406.queue reconstruction by height

Description Link to heading

Solution Link to heading

First, we need sort the vector by height, then do insertion according to ki.

When sorting, we need rewrite the comparing method, in reference to the use of sort() method in C++

Since there may be performance problem when doing insertion frequently in vector, we should use list based on linked list.

Code Link to heading

class Solution {
  public:
    static bool cmp(const vector<int> &a, const vector<int> &b) {
        if (a[0] == b[0])
            return a[1] < b[1];
        return a[0] > b[0];
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>> &people) {
        sort(people.begin(), people.end(), cmp);
        vector<vector<int>> queue;
        for (int i = 0; i < people.size(); i++) {
            int tmp = people[i][1];
            queue.insert(tmp + queue.begin(), people[i]);
        }
        return queue;
    }
};

class Solution {
public:
    // sort by height;
    static bool cmp(const vector<int>& a, const vector<int>& b) {
        if (a[0] == b[0]) 
            return a[1] < b[1];
        return a[0] > b[0];
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort (people.begin(), people.end(), cmp);
        list<vector<int>> que; // list is based on linked list
        for (int i = 0; i < people.size(); i++) {
            int position = people[i][1]; // 
            std::list<vector<int>>::iterator it = que.begin();
            while (position--) { // 
                it++;
            }
            que.insert(it, people[i]);
        }
        return vector<vector<int>>(que.begin(), que.end());
    }
};