Suppose a group of people with disordered order stand 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] indicates that the height of the ith person is hi, and there is ki people whose height is greater than or equal to hi in front.

Please 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 attribute of the jth person in the queue (queue[0] is the person in 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:
The person numbered 0 is 5 in height, and no one taller or the same is ahead of him.
The person numbered 1 is 7 in height, and no one taller or the same is ahead of him.
The person with number 2 is 5 in height, and there are two people who are taller or the same in front of him, that is, the people with numbers 0 and 1.
The person numbered 3 is 6 in height, and one person taller or the same is in front of him, that is, the person numbered 1.
The person with number 4 is 4 in height, and there are four people who are taller or the same in front of him, that is, the people with numbers 0, 1, 2 and 3.
The person numbered 5 is 7 in height, and there is a person taller or the same in front of him, that is, the person numbered 1.
therefore [[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]]

Tips:

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

Problem solving ideas

When everyone's height is different, if we sort them from small to large, we can easily restore the original queue.

For the convenience of narration, we set the number of people as n. after sorting, their heights are h0, h1,..., h(n - 1), and the number in front of the ith person whose height is greater than hi is ki. If we put everyone in the queue in the order after the order, when we put the i-th person:

• The 0,..., i - 1 person has been placed in the queue, and no matter where they stand, they have no effect on the i person, because they are shorter than the i person;

• The i + 1,..., n - 1 person has not been put into the queue, but as long as they stand in front of the i person, they will have an impact on the i person, because they are higher than the i person.

If we initially create an empty queue containing n positions, and each time we put a person in the queue, we will change an "empty" position to a "full" position, then when we put the i-th person in the queue, we need to arrange an "empty" position for him, and there is ki an "empty" position in front of the "empty" position, Used to arrange for taller people in the back. That is, the position of the ith person is the k(i + 1) empty position in the queue from left to right.

Then, if there are people of the same height, the greater than in the above ki definition is not equivalent to the greater than or equal required in the title description. At this time, how should we modify the above method? We can think that if the height of the i-th person is the same as that of the j-th person, i.e. hi = hj, we can reduce the height of the person who is in the later position in the queue a little. In other words, for a certain height value H, we keep the height of the first person with h in the queue unchanged and reduce the height of the second person with H δ， The height of the third person with height h is reduced by 2 δ， And so on, where δ Is a small constant, which makes any person with height h not affect others.

How to find the first, second and third person with height h? We can find that when hi = hj, if ki > kJ, Then it means that I must be at a later position in the queue relative to J (because everyone who is taller than the j-th person must be taller than the i-th person). According to the modified results, hi is slightly smaller than hj, and the i-th person should be put into the queue before the j-th person after sorting. Therefore, we don't really need to modify the height, but just sort according to the ascending order of hi as the first keyword and the descending order of Ki as the second keyword Yes. At this time, people with the same height will be arranged in reverse order according to their positions in the queue, which indirectly reduces the height above δ The effect of this operation.

In this way, we only need to use the method mentioned at the beginning to put the ith person into the k(i + 1) empty position in the queue to get the original queue.

code

	// 406. The cohort was reconstructed according to height
    func reconstructQueue(_ people: [[Int]]) -> [[Int]] {
        
        let newPeople = people.sorted { person1, person2 in
            if person1[0] != person2[0] {
                return ((person1[0] - person2[0]) < 0)
            } else {
                return ((person2[1] - person1[1]) < 0)
            }
        }
        
        let n = newPeople.count
        var ans = [[Int]](repeating: [Int](repeating: 0, count: 0), count: n)
        for person in newPeople {
            var spaces = person[1] + 1
            for i in 0..<n {
                if ans[i].count == 0 {
                    spaces -= 1
                    if spaces == 0 {
                        ans[i] = person
                        break
                    }
                }
            }
        }
        
        return ans
    }