Today’s practice problem is queue reconstruction by height. Let’s work it out.

Article Contents

### Problem

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.

**Constraint**:

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

### Analysis

The question might sound confusing, basically, the given input is a random-arranged list, then we need to reconstruct it following requirements.

First, we sort people list by height `h`

in descending order, which means the tallest one will come first, if height equals, then arrange by `k`

in ascending order.

After that, we place each person into result list using the `k`

position.

Let’s try with the input example.

After first step of sorting by `h`

and `k`

, we have this sorted list `[[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]`

Then we place each person, one by one following the `k`

value of each of them.

```
[[7,0]] (insert [7,0] at index 0)
[[7,0],[7,1]] (insert [7,1] at index 1)
[[7,0],[6,1],[7,1]] (insert [6,1] at index 1)
[[5,0],[7,0],[6,1],[7,1]] (insert [5,0] at index 0)
[[5,0],[7,0],[5,2],[6,1],[7,1]] (insert [5,2] at index 2)
[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] (insert [4,4] at index 4)
```

### Solution

This is solution written in Java.

```
public int[][] reconstructQueue(int[][] people) {
// sort by height in descending order
// if height equal, sort by k in ascending order
Arrays.sort(people, (p1, p2) -> p1[0] == p2[0] ? p1[1] - p2[1] : p2[0] - p1[0]);
// put each person into its k position
List<int[]> res = new LinkedList<>();
for (int[] p: people) {
res.add(p[1], p);
}
return res.toArray(new int[0][]);
}
```

### References

Have fun ~