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.

queue reconstruction

这个快

Pick out tallest group of people and sort them in a subarray (S). Since there's no other groups of people taller than them, therefore each guy's index will be just as same as his k value.
For 2nd tallest group (and the rest), insert each one of them into (S) by k value. So on and so forth.
E.g.
input: [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
subarray after step 1: [[7,0], [7,1]]
subarray after step 2: [[7,0], [6,1], [7,1]]
...

It's not the most concise code, but I think it well explained the concept.

class Solution(object):
    def reconstructQueue(self, people):
        if not people: return []

        # obtain everyone's info
        # key=height, value=k-value, index in original array
        peopledct, height, res = {}, [], []

        for i in xrange(len(people)):
            p = people[i]
            if p[0] in peopledct:
                peopledct[p[0]] += (p[1], i),
            else:
                peopledct[p[0]] = [(p[1], i)]
                height += p[0],

        height.sort()      # here are different heights we have

        # sort from the tallest group
        for h in height[::-1]:
            peopledct[h].sort()
            for p in peopledct[h]:
                res.insert(p[0], people[p[1]])

        return res

但速度不快

class Solution {
public:
    vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
        list<tuple<int,int,int>> tuples;
        for(int i=0;i<people.size();i++){
            tuples.push_back(make_tuple(people[i].first,people[i].second,people[i].second));
        }
        vector<pair<int,int>> res;
        while(tuples.size()>0){
            //find minimum with 0
            int minh=-1;
            list<tuple<int,int,int>>::iterator it_del;
            for(auto it=tuples.begin();it!=tuples.end();++it){
                if(get<2>(*it)==0){
                    if(get<0>(*it)<minh || minh==-1){
                      minh=get<0>(*it);
                      it_del=it;
                    }
                }
            }
            res.push_back(make_pair(minh,get<1>(*it_del)));
            tuples.erase(it_del);
            //update rest
            for(auto& it:tuples){
                if(get<0>(it)<=minh){
                    get<2>(it)=get<2>(it)-1;
                }
            }
        }
        return res;
    }
};