406. Queue Reconstruction by Height

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers(h, k), wherehis the height of the person andkis the number of people in front of this person who have a height greater than or equal toh. Write an algorithm to reconstruct the queue.

Note:
The number of people is less than 1,100.

Example

Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

S： greedy O(n^2)

排序后从后往前插入。注意排序时同一高度的两数k值小的排在后面，这样可以先插入，避免错乱

因为每次新插入的都是比已插入的数小的数，只要插入在第k位，一定可以满足条件

    vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
        vector<pair<int, int>> result;
        sort(people.begin(), people.end(), cmpFirst);
        for (int i = people.size() - 1; i >= 0; --i) {
            int idx = people[i].second;
            if (idx >= result.size()) {
                result.push_back(people[i]);
            } else {
                result.insert(result.begin() + idx, people[i]);
            }
        }
        return result;
    }
    static bool cmpFirst(pair<int, int> a, pair<int, int> b) {
        if (a.first < b.first) return true;
        else if (a.first == b.first) return a.second > b.second;
        else return false;
    }