requirements

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], [7, 1], [5, 0], [6, 1], [5, 2]] output: [[5, 0), (7, 0], [5, 2], [6, 1], [4], [7, 1]] : 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.Copy the code

Example 2:

Input: people = [[6, 0], [5, 0], [4, 0], [3, 2], [2], [1, 4]] output: [[4, 0], [5, 0], [2], [3, 2], [1, 4], [6, 0]]Copy the code

Tip:

  • 1 <= people.length <= 2000
  • 0 <= hi <= 106
  • 0 <= ki < people.length
  • The problem data ensures that the queue can be rebuilt

The core code

class Solution:
    def reconstructQueue(self, people: List[List[int]]) - >List[List[int]] :
        people = sorted(people,key=lambda x:(-x[0],x[1]))
        res = []
        for p in people:
            res.insert(p[1],p)
        return res
Copy the code

1. Rank them in order of height from high to low. If they are of the same height, rank them in order of k from small to large. Insert: Inserts new arrays one by one in sorted order, in positions k

As example, the sorting out: [(7, 0), (7, 1], [6, 1], [5, 0], [5, 2], [4]] insert process: first insert: the second plug: [(7, 0]] [[7, 0), (7, 1]] the third plug: [(7, 0), (6, 1), (7, 1]] insert 4: [[5, 0), (7, 0), (6, 1), (7, 1]]… First inserted high, after inserted short, even after inserted into the front will not have images, because of short, a better problem.