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 ~
