LeetCode_ 406_ Rebuild the queue based on height

Topic link

• https://leetcode.cn/problems/queue-reconstruction-by-height/

Title Description

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

Tips ：

• 1 <= people.length <= 2000
• 0 <= hi <= 10^6
• 0 <= ki < people.length
• The topic data ensures that the queue can be rebuilt

Their thinking

The law of greed

• Sort by height , For those with the same height k From small to large

AC Code

class Solution {
    
    public int[][] reconstructQueue(int[][] people) {
    
        Arrays.sort(people, (a, b) -> {
    
            if (a[0] == b[0]) {
    
                return a[1] - b[1];
            }
            return b[0] - a[0];
        });
        LinkedList<int[]> ans = new LinkedList<>();
        for (int[] p : people) {
    
            ans.add(p[1], p);
        }
        return ans.toArray(new int[people.length][]);
    }
}