# 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.

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

**Example**

Solution:

<?php class Solution { /** * @param Integer[][] $people * @return Integer[][] */ function reconstructQueue($people) { usort($people, function($p1, $p2){ return ($p1[0] !== $p2[0])? $p2[0] <=> $p1[0] : $p1[1] <=> $p2[1]; }); $result = []; foreach($people as $p){ array_splice($result, $p[1], 0, [$p]); } return $result; } } ?>

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

The higher the person is, the more importance it has for other persons

- So starting sort by height, DESC
- Then for each height level, sort by # of higher heads in the front, ASC
- (Just like ‘ORDER BY h DESC, k ASC’ in SQL)

Now we have:

More Important to Others <===> Less Important to Others

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

Then set group height = 7 to the result

[7,0] [7,1] ; TBD: [6,1] [5,0] [5,2] [4,4]

Now set group height = 6. It could be places any where, since h=7 can’t see them, so the position is determined by their value of k. for example: [6,1]. there’s one higher/equal height person ahead, we can simply insert it right after k is matched, and push everyone else backwards safely since they don’t care about lower person moving around.

0 1 2 3 4 ..... (index) [7,0] [6, 1] [7,1] ; TBD: [5,0] [5,2] [4,4] [5,0] [7,0] [6, 1] [7,1] ; TBD: [5,2] [4,4] [5,0] [7,0] [5,2] [6, 1] [7,1] ; TBD: [4,4] [5,0] [7,0] [5,2] [6, 1] [4,4] [7,1]

In PHP, `array_splice($result, $p[1], 0, [$p]); `

means insert p to position p[i] and move people behind backwards

In Java, LinkedList seems easier.

In Python, there’s even easier method (list.insert(index, value))

## 0 Comments