218. Rebuild the Queue
People stand in a line at a ticket counter, but a gust of wind scrambled them. Each person is described by a pair [h, k]: h is their height and k is the number of people standing in front of them in the line who are at least as tall as they are (equal heights count). The pairs in people are given in no particular order.
Rebuild the line from front to back and return it as an array of the same [h, k] pairs. The input always describes at least one valid line, and the line is then unique up to people that are exactly identical.
For instance, the pairs [[4, 1], [6, 0], [4, 0]] rebuild to [[4, 0], [6, 0], [4, 1]]: the last person (height 4) has one taller-or-equal person, the 6, in front, and the first person has nobody in front at all.
Example 1
- Input:
- people = [[150,3],[172,0],[165,0],[168,1],[150,1]]
- Output:
- [[165,0],[150,1],[172,0],[150,3],[168,1]]
- Explanation:
The line is 165, 150, 172, 150, 168. The 150 at the second place has one person (165) at least as tall in front. The 150 at the fourth place has three (165, 150, 172). The 168 has only the 172 in front.
Example 2
- Input:
- people = [[9,0]]
- Output:
- [[9,0]]
- Explanation:
A single person stands alone.
Example 3
- Input:
- people = [[5,2],[5,0],[5,1]]
- Output:
- [[5,0],[5,1],[5,2]]
- Explanation:
Equal heights count, so the people of height 5 stand in the order of their k values.
Constraints
1 ≤ people.length ≤ 30000
0 ≤ h ≤ 106
0 ≤ k < people.length
The input always describes a valid line.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)