Queue Reconstruction by Height

0
222
Queue Reconstruction by Height
Queue Reconstruction by Height

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

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 ~