406-queue-reconstruction-by-height.md

406. Queue Reconstruction by Height - 根据身高重建队列

假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。 编写一个算法来重建这个队列。

注意：
总人数少于1100人。

示例

输入:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

输出:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

---

题目标签：Greedy

题目链接：LeetCode / LeetCode中国

题解

Language	Runtime	Memory
cpp	32 ms	1.1 MB

class Solution {
public:
    vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
        auto cmp = [](pair<int, int>& p1, pair<int, int>& p2) {
            if (p1.first != p2.first) {
                return p1.first > p2.first;
            } else {
                return p1.second < p2.second;
            }
        };
        sort(people.begin(), people.end(), cmp);
        vector<pair<int, int> > res;
        for (auto p : people) {
            res.emplace(res.begin()+p.second, p);
        }
        return res;
    }
};