406. reconstruct the queue based on height

406. Rebuild the queue according to height

Let's say there's a group of people in a disordered order standing in a line , Array people Properties that represent some people in the queue （ Not necessarily in order ）. Every people[i] = [hi, ki] It means the first one i The height of an individual is hi , front Just right Yes ki Height greater than or equal to hi People who .

Please reconstruct and return the input array people The queue represented by . The returned queue should be formatted as an array queue , among queue[j] = [hj, kj] It's number one in the queue j Personal attributes （queue[0] It's the people at the front of the line ）.

Example 1：

Input ：people = [[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]]
explain ：
The number is 0 The height of a person who is 5 , No one is taller or the same in front of him .
The number is 1 The height of a person who is 7 , No one is taller or the same in front of him .
The number is 2 The height of a person who is 5 , Yes 2 A taller or the same person is in front of him , That is, the number is 0 and 1 People who .
The number is 3 The height of a person who is 6 , Yes 1 A taller or the same person is in front of him , That is, the number is 1 People who .
The number is 4 The height of a person who is 4 , Yes 4 A taller or the same person is in front of him , That is, the number is 0、1、2、3 People who .
The number is 5 The height of a person who is 7 , Yes 1 A taller or the same person is in front of him , That is, the number is 1 People who .
therefore [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] It's the reconstructed queue .
Example 2：

Input ：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
Output ：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

reflection

We consider People There are two dimensions high( height )、pre( The number of people in front )

We certainly can't think of two dimensions together , So much so that the head and the tail .

Let's first consider high

Yes people Execute collation ：

• high The big one is in front
• high identical ,pre The small one is in the front

Before sorting :[[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]]

Why do we think so ？

Why is the tall one in front ？

We can iterate over the sorted people Array , Insert operation , Insert at pre.

Because the tall one is in front , Therefore, the subsequent insertion has no effect on the previously inserted ones .

The process of insertion :

• Insert [7,0]：[[7,0]]
• Insert [7,1]：[[7,0],[7,1]]
• Insert [6,1]：[[7,0],[6,1],[7,1]]
• Insert [5,0]：[[5,0],[7,0],[6,1],[7,1]]
• Insert [5,2]：[[5,0],[7,0],[5,2],[6,1],[7,1]]
• Insert [4,4]：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

Code implementation

    public int[][] reconstructQueue(int[][] people) {
    
        Arrays.sort(people, new Comparator<int[]>() {
    
            @Override
            public int compare(int[] o1, int[] o2) {
    
                if(o2[0]==o1[0]){
    
                    return o1[1]-o2[1];
                }
                return o2[0]-o1[0];
            }
        });
        ArrayList<int[]> list=new ArrayList<>();
        for (int i=0;i<people.length;i++){
    
            int postion=people[i][1];
            list.add(postion,people[i]);
        }
        return  list.toArray(new int[people.length][people[0].length]);
    }