“This is the 19th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021”

describe

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], [7, 1], [5, 0], [6, 1], [5, 2]] Output: [[5, 0), (7, 0], [5, 2], [6, 1], [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 the person 1. Hence the [[5, 0), (7, 0], [5, 2], [6, 1], [4], [7, 1]] is the reconstructed the queue.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

Note:

  • 1 <= people.length <= 2000
  • 0 <= hi< = 10 ^ 6
  • 0 <= ki < people.length
  • It is guaranteed that the queue can be reconstructed.

parsing

Given a group of people, this is the attribute of some people in the queue. Each people[I] = [hi, ki] represents the ith person of hi height preceded by ki and other people of hi height or greater. They ask you to refactor and return the queue represented by the input array people. The returned queue should be formatted as a new array queue, where Queue [j] = [hj, kj] is the attribute of the JTH person in the queue (queue[0] is the first person in the queue).

Let’s rearrange the elements in people to satisfy the height and position attributes of each element, and return the array. In order to meet the requirement of the number of people whose height is greater than or equal to their own, the height h is first arranged in descending order, and the height K is also arranged in ascending order, and then the position we insert is considered according to K. For example, change the first example:

[[7, 0], [4], [7, 1], [5, 0], [6, 1], [5, 2]] - > [(7, 0), (7, 1], [6, 1], [5, 0], [5, 2], [4]]Copy the code

Then define an empty list result and start iterating over the above list for inserts:

Insert into index 0: [[7,0]] [7,1] insert into index 1: [[7,0]] [7,1] insert into index 1: [[7, 0), (7, 1]] of [6, 1) is inserted into the index to 1, the front have a height greater than or equal to his people: [(7, 0), (6, 1], [7, 1]], [5, 0] the location of the insert to the index of 0, the front have zero height is greater than or equal to his people: Insert [[5, 0], [7, 0], [6, 1], [7, 1]] [5,2] insert into position 2 where there are two persons whose height is greater than or equal to him: [[5, 0], (7, 0], [5, 2], [6, 1], [7, 1]], [4] into the index for 4 place, just in front of the four height is greater than or equal to his people: [[5, 0], [7, 0], [5, 2], [6, 1], [4, 4], [7, 1]Copy the code

answer

class Solution(object):
    def reconstructQueue(self, people):
        """
        :type people: List[List[int]]
        :rtype: List[List[int]]
        """
        people.sort(reverse=True)
        result = []
        for h,k in sorted(people, key=lambda x: (-x[0], x[1])):
            result.insert(k, [h,k])
        return result
        	      
		
Copy the code

The results

Linked submissions in Python online submissions for Queue Reconstruction by Height. Memory Usage: Submissions in Python online submissions for Queue Reconstruction by Height.Copy the code

Original link: leetcode.com/problems/qu…

Your support is my biggest motivation