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.

Input

• people - List of pairs (h, k)

Approach

The best thing to do here is to carefully observe an example input/output of the problem:

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

Notes:

• The k value represents the index of the output array for some of the pairs. For example, [5,2] is at index 2, [5,0] is at index 0, [4,4] is at index 4.
• Pairs with the same height h but different k values are represented in ascending order. Observe that [5,0] is before [5,2], [7,0] is before [7,1], etc.

Let's think about the 1st bullet point. Pairs with k = 0 include [5,0] and [7,0]. If k represents the index number, it clearly does not make sense for two values to have index 0. Since the output shows that [5,0] is at index 0, and not [7,0], it can be deduced that the [7,0] pair may have been at index 0 at one point, but was pushed away after the [5,0] pair was inserted. If that is the case, the insertion of pairs seem to occur in the order of descending height. This makes more sense as the [4,4] pair would be the last element to insert, and this pair is fixed at its rightful location (index 4) without being pushed away.

Let's now look at the 2nd bullet point. If the insertion of pairs occur in the order of descending height, what about the value k? For example, if we look at pairs of h = 5, we can either choose to insert the [5,0] pair first, or the [5,2] pair first. If we add the [5,0] pair first, then the [5,2] pair second, we do not have to re-evaluate the [5,0] pair because the position of this pair is not affected by the insertion of the [5,2] pair. However, if we insert the [5,2] pair first, and then we insert the [5,0] pair second, the [5,2] pair can be affected since a new element is added in front of the [5,2] pair. In this case, since the height constraint (a person's height has to be greater than or equal to h) is satisfied, the [5,2] pair will now turn into [5,3]. Since we are not supposed to change any of the pair values here, this is clearly the wrong approach. It then follows that the insertion of pairs occur in the order of descending height (descending h) and ascending number of people in front of the person (ascending k).

The key to the algorithm of this problem is to use the insert() API, which allows you to insert elements at a specific index and shift elements at that index formerly, and all other indices to the right of it, by 1.

Solution

from functools import cmp_to_key  
class Solution:  
    def reconstructQueue(self, people):
        """
        :type people: List[List[int]]
        :rtype: List[List[int]]
        """

        def _comparator(x, y):
            if y[0] != x[0]:  # descending h
                return y[0] - x[0]
            else:  # ascending k
                return x[1] - y[1]

        result = []
        for h, k in sorted(people, key=cmp_to_key(_comparator)):
            result.insert(k, [h, k])
        return result