**Solution**

**Queue Reconstruction by Height** https://leetcode.com/problems/queue-reconstruction-by-height/

**Problem Insights**

- Think about the shortest person. Say his height is 4 and his k value is also 4. In the reconstructed queue, what index should he be at? The answer is at index k since there are k people with height greater than equal to h.
- So say we remove the shortest person, solve the problem, and then add the shortest person - we are done. Example:[[5,0], [7,0], [5,2], [6,1], [7,1]] - Without [4,4] (the smallest height). Now 4,4 can be inserted into its index.
- What about the sub-problem? Again remove the shortest persons [5,0] and [5,2], solve the remaining problem and insert shortest problem.

**Algorithm**

- Find the tallest people and sort them by their k value. Their k value must be either 0, 1, 2, 3.. since their k value is exclusively derived by "people of height equal" since no one is available with a greater height.
- Now find the next tallest person. Sort them by their k value and insert them into the list using k value as index. The k value acts as their rank.
- Repeat the process.

```
class Solution(object):
def reconstructQueue(self, people):
"""
:type people: List[List[int]]
:rtype: List[List[int]]
"""
people_dict = {}
for p in people:
h,k = p[0], p[1]
people_dict.setdefault(h, [])
people_dict[h].append(k)
result = []
for h in sorted(people_dict.keys(), reverse=True):
people_dict[h].sort()
for k in people_dict[h]:
result.insert(k, [h,k])
return result
```