# 0406. Queue Reconstruction by Height
###### tags: `Leetcode` `Medium` `Greedy` `Sorting`
Link: https://leetcode.com/problems/queue-reconstruction-by-height/
## 思路 $O(NlogN)$ $O(1)$
由于矮的怎么排对于高的没有影响，高的怎么排对矮的有影响
所以解决方法就是先排高的，后面一个人来了之后，看它的k值是几就把它插在index为几的位置
这里注意comparator的写法里面如果a[0]==b[0]那么按a[1]-b[1]排的原因是如果先把大的插进去，可能list本身没有那么大会造成IndexOutOfBoundException, 排除这个问题，其实不需要一定按照a[1]-b[1]排
**只有list里面装的是int类型的变量的时候才可以直接ans.toArray(new int[n][2])**
## Code

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, new Comparator<int[]>(){
            public int compare(int[] a, int[] b){
                return a[0]==b[0]?a[1]-b[1]:b[0]-a[0];
            }
        });
        List<int[]> ans = new ArrayList<>();
        for(int[] info:people){
            ans.add(info[1], info);
        }
        
        int n = people.length;
        return ans.toArray(new int[n][]);
    }
}