Queue Reconstruction by Height

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.

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

Concise Sorting and list.add(index, element) Solution: O(n^2) time

public class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (p1, p2) -> p1[0] == p2[0] ? p1[1] - p2[1] : p1[0] - p2[0]); //Sort in descending order
        LinkedList<int[]> list = new LinkedList<>();
        for (int i = 0; i < people.length; i++) list.add(people[i][1], people[i]);
        return list.toArray(people); //list.toArray() will return Object[], we need int[][] 
    }
}

Analysis

The idea in this solution is that
We first sort the people with height and then number of people front in descending order
Then we insert people from higher to lower
Because inserting at existing index will shift current element to the right
We are able to put shorter person before the higher person Notice that because of list.add(index) costs O(n) time, total time for this solution is O(n^2) time