406. Queue Reconstruction by Hei

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

一刷
题解：思路很巧妙

1. 排序：高的在前，若一样高，k小的在前。
2. 用LinkedList, 把<h, k>插入到位置k

因为，比如之前的位置是<h1, k1>, 现在出现了<h2, k2>， 那么必然有h2<h1, 那么不论插入到<h1, k1>之前还是之后，都不影响k1

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        //pick up the tallest guy first
        //when insert the next tall guy, just need to insert him into kth position
        //repeat until all people are inserted into list
        Arrays.sort(people, new Comparator<int[]>(){
            public int compare(int[] a, int[]b){
                if(a[0]!=b[0]) return b[0]-a[0];
                else return a[1]-b[1];
            }
        });
        List<int[]> res = new LinkedList<>();
        for(int[] cur :people){
            res.add(cur[1], cur);
        }
        return res.toArray(new int[people.length][]);//revert to int[][]
    }
}