Comment on page

# 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)`, 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]]
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
Last modified 4yr ago