> For the complete documentation index, see [llms.txt](https://code.taozirui.com/lc/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code.taozirui.com/lc/greedy/queue-reconstruction-by-height.md).

# 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)**

```python
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:

```python
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](https://leetcode.com/djrochford) and the second is from [YJL1228](https://leetcode.com/yjl1228) in this [post](https://leetcode.com/problems/queue-reconstruction-by-height/discuss/89345/Easy-concept-with-PythonC++Java-Solution)