You can consider people from the shortest.

The shortest in your example is the one with a pair [4, 4] . You know that there is no shorter there so he must be in 5th position (because he needs 4 higher people). And then you can go recursively :P Sorry for my awful english xd

edit

Ok, maybe i'll write it more precisely. The idea is to consider the people in some order and assign positions to them greedily.

Ok so you sorted the pairs. Suppose for now that the heights are unique. Think about such a situation: we want to place some person, shorter are already placed and higher aren't. So in fact if the person's pair is (h, k) you want to find a place in front of which there are k empty positions (because there will be placed higher people in the future).

edit2

It is easy to make it work for orignal problem :P

The following is a simple priority-queue based C++ solution.

Note that people are sorted using the priority-queue in a descending order by their height first.

Then, if two or more people have the same height, they are sorted in an ascending order by the number of people in front of them ( the second field of the pair inserted in the queue is INT_MAX - k instead of k ).

After inserting all persons to the priority-queue, r.begin() + k, is the required position to insert the present person at the top of the priority-queue in the present reconstructed queue r.

This operation is iterated until all persons are removed from the priority-queue and inserted at the required positions in r.

class Solution 
{
    typedef pair< int, int >   pair_t;
    
    typedef vector< pair_t > vector_t;
    
public:
    vector_t reconstructQueue( vector_t& people ) 
    {
        priority_queue< pair_t > q; vector_t r;
        
        for( auto p: people )
            q.emplace( p.first, INT_MAX - p.second );

        for( int h, k; !q.empty(); q.pop() )
            h = q.top().first, 
            k = INT_MAX - q.top().second,  
            r.emplace( r.begin() + k, h, k );
        
        return r; 
    }
};

For the given example, the priority-queue after inserting all people (with the original k) is:

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

The reconstructed queue r after each insertion operation is:

1. [7,0] at position 0: [[7,0]]

2. [7,1] at position 1: [[7,0],[7,1]]

3. [6,1] at position 1: [[7,0],[6,1],[7,1]]

4. [5,0] at position 0:[[5,0],[7,0],[6,1],[7,1]]

5. [5,2] at position 2: [[5,0],[7,0],[5,2],[6,1],[7,1]]

6. [4,4] at position 4: [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]