“This is the third day of my participation in the First Challenge 2022. For details: First Challenge 2022”

The title

Suppose you have an out-of-order group of people standing in a queue, and the array people represents the attributes of some people in the queue (not necessarily in order). Each people[I] = [hi, ki] means that the ith person is hi, and there are exactly ki people in front of them who are hi or higher.

You reconstruct and return the queue represented by the input array people. The returned queue should be formatted as an array queue, where Queue [j] = [hj, kj] is the property 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], [7, 1]]

  • Explanation:

    • The person numbered 0 is 5 tall, and no one is taller or the same height.
    • The person numbered 1 is 7, and no one is taller or the same height.
    • Number 2 is 5 tall, and there are two taller or equal people in front of him, number 0 and number 1.
    • Person number 3 is 6 tall, and there is a taller or equal person in front of him, person number 1.
    • The person numbered 4 is 4 in height, and there are 4 taller or equal people in front of him, namely, 0, 1, 2 and 3.
    • Person number 5 is 7 tall, and there is a taller or equal person in front of him, person number 1.
    • Therefore [(5, 0), (7, 0], [5, 2], [6, 1], [4], [7, 1]] is the queue after restructuring.

Example 2:

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

Tip:

  • 1 <= people.length <= 2000
  • 0 <= hi <= 10^6
  • 0 <= ki < people.length

The problem data ensures that the queue can be rebuilt

solution

After sorting according to height, the queue is inserted according to the k of people with height first. The nodes inserted in the latter order will not affect the nodes inserted before, and the queue is finally completed according to the rules of K.

So after sorting by height from largest to smallest:

Local optimal: the priority is to insert according to the k of the tall people. The people after the insert satisfies the queue attribute

Global optimality: at the end of the insertion operation, the entire queue meets the problem queue attribute

Local optimality leads to global optimality. If you can’t find a counterexample, try greed.

First of all, tall people can ignore short people, as long as I am tall and sorted, adding more people shorter than me in the middle or next to me will not affect my results. 1. Sort by height, descending or ascending if the height is the same 2. Loop, insert each height into the corresponding position.

var reconstructQueue = function(people) {
    let ans=[];
    if(! people||! people.length){return []}
    people.sort((a,b) = >{
        if(a[0]===b[0]) {return a[1]-b[1]}else{
            return b[0]-a[0]
        }
    })
    people.forEach(item= >{
        ans.splice(item[1].0,item)
    })
    return ans;
};
Copy the code