Difficulty: Medium
Problem Link: https://leetcode.com/problems/queue-reconstruction-by-height/

Problem

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. 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]]
Tag: Greedy

Explanation

• 這道題目的關(guān)鍵是：只有身高大于等于自身的人，對于K值才有影響。假設(shè)A的身高為h，身高大于等于h的人的站位會影響A的K值，而身高小于h的人無論是站在A的前面抑或是后面，對于A的K值都是沒有影響的。但是A的站位卻會影響比A身高矮的人的K值，所以唯有先確定A的站位，才可確定身高小于A的人的站位，所以初步猜想是將所有人按照身高從高到低排序，依次插入到一個新的隊列中去，插入的位置就是K值的大小。
• 第二個要考慮的問題就是身高相同的人，但是K值不同，顯然K值越大的人站位越靠后，因為對于H相同的人，站位靠后的K值至少比前面的大1。所以要先插入K值較小的人。因此得出這樣的排序規(guī)則。
  auto comp = [](const pair<int, int>& x, const pair<int, int>& y) { return (x.first > y.first || (x.first == y.first && x.second < y.second)); };

cpp solution

class Solution {
public:
    vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
        auto comp = [](const pair<int, int>& x, const pair<int, int>& y) {
            return (x.first > y.first || (x.first == y.first && x.second < y.second));   
        };
        
        sort(people.begin(), people.end(), comp);
        vector<pair<int, int>> res;
        
        for (auto &p : people) {
            res.insert(res.begin() + p.second, p);
        }
        
        return res;
    }
};