406 Queue Reconstruction by Height

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

The Idea: Sort by h descending and then by k ascending. Then iterate through this new array, and insert by position k. Sorted by height ensures that when we insert by position k, that every iteration is correct all the way through.

For example:

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

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

for loop:
[[7, 0]]
[[7, 0], [7, 1]]
[[7, 0], [6, 1], [7, 1]]
[[5, 0], [7, 0], [6, 1], [7, 1]]
[[5, 0], [7, 0], [5, 2], [6, 1], [7, 1]]
[[5, 0], [7, 0], [5, 2], [6, 1], [4, 4], [7, 1]]

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

Complexity: O(nlogn + n) time and O(n) space

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

        sol = []
        sorted_p = sorted(people, key=lambda x: (-x[0], x[1]))
        for person in sorted_p:
            sol.insert(person[1], person)
        return sol