Level

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;
    }
}
public class Queue_Reconstruction_by_Height {

    /*
    Pick out tallest group of people and sort them in a subarray (S). Since there's no other groups of people taller than them, therefore each guy's index will be just as same as his k value.
    For 2nd tallest group (and the rest), insert each one of them into (S) by k value. So on and so forth.

    E.g.

    input: [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
    subarray after step 1: [[7,0], [7,1]]
    subarray after step 2: [[7,0], [6,1], [7,1]]

     */
    class Solution {
        public int[][] reconstructQueue(int[][] people) {

            // maxheap to hold list of people in comparison with height and then use k to order the same height people
            PriorityQueue<int[]> pq = new PriorityQueue<>(
                (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0]
            );

            for (int[] each: people) {
                pq.offer(each);
            }

            // now pq is: [[7,0], [7,1], [6,1], [5,0], [5,2]], [4,4]

            List<int[]> result = new ArrayList<>();

            // [[7,0],
            // [[7,0], [7,1],
            // [[7,0], [6,1], [7,1]]
            while (!pq.isEmpty()) {
                int[] each = pq.poll();
                result.add(each[1], each);
            }

            return result.toArray(people);

        }
    }
}

All Problems

All Solutions