# Queue Reconstruction by Height

0
1971

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 == p2 ? p1 - p2 : p2 - p1);

// put each person into its k position