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

Thoughts:

1. Sort the h in descending order and k in ascending order.
2. Traverse the sorted list and insert the current person into kth position of new list.

Code T: O(n^2) S:O(n)

``````class Solution(object):
def reconstructQueue(self, people):
"""
:type people: List[List[int]]
:rtype: List[List[int]]
"""
people.sort(key = lambda x: [-x[0], x[1]])
result = []
for [h, k] in people:
result.insert(k, [h,k])
return result
``````

more explicit way: first group the height, then sort in each group, then insert into the final list:

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

# sort the h, and then sort the k and insert into kth postiion in new list
peopledict, height, res = {}, [], []
for i in range(len(people)):
p = people[i]
if p[0] not in peopledict:
peopledict[p[0]] = [(p[1], i)]
height+= p[0],
else:
peopledict[p[0]] += (p[1], i),

height.sort(reverse=True)
for h in height:
peopledict[h].sort()
for k, i in peopledict[h]:
res.insert(k, people[i])
return res
``````

the first solution is from djrochford and the second is from YJL1228 in this post