Medium

## Description

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.

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


## Solution
First sort the array people in the following order. Suppose person1 and person2 are two elements of people, then person1 is before person2 if and only if person1[0] > person2[0] or person1[0] == person2[0] and person1[1] < person2[1]. That is, sort the people according to height in descending order. If two people have the same height, sort them according to count in ascending order.

Next use the idea of insertion sort to reconstruct the array. For index i from 1 to people.length - 1, people[i]'s height must be less than or equal to all the people in the index range from 0 to i - 1. Suppose count = people[i][1]. If count < i, then insert people[i] at index count.

Take the example in the problem. The array is reconstructed in the following way.

The input: [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]].

After sorting: [[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]].

First insertion: [7,1] is at the correct index, so do not change.

Second insertion: Insert [6,1] at index 1. The array becomes [[7,0], [6,1], [7,1], [5,0], [5,2], [4,4]].

Third insertion: Insert [5,0] at index 0. The array becomes [[5,0], [7,0], [6,1], [7,1], [5,2], [4,4]].

Fourth insertion: Insert [5,2] at index 2. The array becomes [[5,0], [7,0], [5,2], [6,1], [7,1], [4,4]].

Fifth insertion: Insert [4,4] at index 4. The array becomes [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]].

And the reconstructed array is [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]].

Java
java
class Solution {
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people, new Comparator<int[]>() {
public int compare(int[] person1, int[] person2) {
if (person1[0] != person2[0])
return person2[0] - person1[0];
else
return person1[1] - person2[1];
}
});
int length = people.length;
for (int i = 1; i < length; i++) {
int[] person = people[i];
int height = person[0], count = person[1];
if (count < i) {
for (int j = i - 1; j >= count; j--) {
for (int k = 0; k < 2; k++)
people[j + 1][k] = people[j][k];
}
people[count][0] = height;
people[count][1] = count;
}
}
return people;
}
}
`