leetcode 406. Queue reconstruction by height

You are given an array of people, people, which are the attributes of some people in a queue (not necessarily in order). Each people[i] = [hi, ki] represents the ith person of height hi with exactly ki other people in front who have a height greater than or equal to hi.

Reconstruct and return the queue that is represented by the input array people. The returned queue should be formatted as an array queue, where queue[j] = [hj, kj] is the attributes of the jth person in the queue (queue[0] is the person at the front of the queue).

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]]
Explanation:
Person 0 has height 5 with no other people taller or the same height in front.
Person 1 has height 7 with no other people taller or the same height in front.
Person 2 has height 5 with two persons taller or the same height in front, which is person 0 and 1.
Person 3 has height 6 with one person taller or the same height in front, which is person 1.
Person 4 has height 4 with four people taller or the same height in front, which are people 0, 1, 2, and 3.
Person 5 has height 7 with one person taller or the same height in front, which is person 1.
Hence [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] is 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]]

people Each group in the array is [ height , There are several people who are taller than me or as tall as me ]
Press “ There are several people taller than me in front ” Order the array

Ideas ：

First of all, make it clear , Suppose we have arranged the order now , Those who are taller than me in front 3 personal , Then adding a shorter one to the front will not affect the current order .
But adding a taller one in front of me will have an impact , The one higher than me in front is 4 Personal .

therefore , The first people According to height （people[i][0]） null , Make sure the high ones are lined up first , Then add the short one , Will not affect the order .

people[i] = [hi, ki], ki It means that there is ki Personal than the current i individual people high ,
Because it is arranged from high to low according to height , The existing ones in front are better than the current people high , So just put him insert To the first ki A place ,
Then the short one from behind insert It doesn't matter to go in front of him , No effect ki.
Understanding this is the key .

How do two people of the same height line up , It's the one in front （ki smaller ） Or the back （ki The larger ）？
Just imagine , If the one behind first , such as (5,4)： Height is 5 People who , There is 4 Someone taller than him or as tall as him ,
One more （5,2）, want insert To the first 2 individual , stay (5,4) In front of , So good , There is another one as tall as him in front ,(5,4) Should become （5,5） 了 , Be affected by .

therefore , If you're the same height , First row ki smaller .

public int[][] reconstructQueue(int[][] people) {
    
    int n = people.length;
    Arrays.sort(people, (a, b)->(a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]));
    List<int[]> res = new LinkedList<>();
    
    for(int[] tmp : people) {
    
        res.add(tmp[1], tmp);
    }
    return res.toArray(people);
}