406. Queue Reconstruction by Height -M

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]]

A:

每次 按照height 拿出最小的。 放到结果相应的位置。
We put people in an array of length n. The number k means that we should put this person in the kth empty position from the beginning. The empty position mean that there will be higher or equal height person coming in here, so leave these positions out first. For everyone, we should first insert the lower h person. For the person who has same h we should first insert the person has larger k value. For everyone to put in, it takes O(n) time to find kth empty position, so it will take the O(n^2) time for all people.
E.g.
input: [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
sort: [[4,4], [5,2], [5,0], [6,1], [7,1], [7,0]]
step1: [[  ,  ], [  ,  ], [  ,  ], [  ,  ], [4,4], [  ,  ]]
step2: [[  ,  ], [  ,  ], [5,2], [  ,  ], [4,4], [  ,  ]]
step3: [[5,0], [  ,  ], [5,2], [  ,  ], [4,4], [  ,  ]]
step4: [[5,0], [  ,  ], [5,2], [6,1], [4,4], [  ,  ]]
step5: [[5,0], [  ,  ], [5,2], [6,1], [4,4], [7,1]]
step6: [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        vector<vector<int>> res(people.size(), {INT_MAX, INT_MAX}); // height can not be negative
        struct comp{
            bool operator()(const vector<int> &a, const vector<int> b){
                return a[0] == b[0]? a[1]>b[1] : a[0]>b[0];
            }
        };        
        // default is max_heap, use greater() or > for min-heap
        priority_queue<vector<int>, vector<vector<int>>, comp > minH(people.begin(), people.end());
        
        // find the remaining min-hight, and place on k_th empty places
        while(not minH.empty()){
            auto tmp = minH.top();
            minH.pop();                                                             
            // find the index to solve
            int count = 0;
            for(int i =0;i<res.size();i++){
                if(res[i][0] >= tmp[0]){  // skip count of the values that smaller
                    if(count++ == tmp[1]){
                        res[i] = tmp;
                        break;  
                    }
                }
            }
        }
        return res;
    }
};

看这里的discussion