Description
People are described by (h, k) where h is height and k is the number of people in front with height >= h. Reconstruct and return the queue.
Examples
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:
Sorted by height desc, insert by k.
Input:
people = [[1]]Output:
[1]Explanation:
Minimal case with a single-element matrix.
Input:
people = [[6,0],[3,1],[8,0],[4,2],[9,1],[5,3]]Output:
[[6,0],[8,0],[3,1],[9,1],[4,2],[5,3]]Explanation:
Sort by height descending: [9,1],[8,0],[6,0],[5,3],[4,2],[3,1]. Insert each person at index k: insert [9,1] at index 1 → [[9,1]], insert [8,0] at index 0 → [[8,0],[9,1]], insert [6,0] at index 0 → [[6,0],[8,0],[9,1]], insert [5,3] at index 3 → [[6,0],[8,0],[9,1],[5,3]], insert [4,2] at index 2 → [[6,0],[8,0],[4,2],[9,1],[5,3]], insert [3,1] at index 1 → [[6,0],[3,1],[8,0],[4,2],[9,1],[5,3]]. Final rearrangement gives the correct queue order.
Constraints
- •
1 ≤ people.length ≤ 2000