All problems

Queue Reconstruction by Height

Medium · greedy

A group of people stand in a single line. Each person is described by a pair [height, k]: their height, and k, the number of people standing in front of them who are at least as tall as they are (a person of exactly the same height counts).

You are given the pairs in no particular order. Rebuild the line and return it as a list of the same pairs, from the front of the line to the back.

The input always describes exactly one valid line.

Examples

Example 1

Input: people = [[2, 3], [6, 1], [4, 0], [6, 0], [2, 1]]

Output: [[4, 0], [2, 1], [6, 0], [2, 3], [6, 1]]

The last person (height 6) has one person at least as tall in front of them, the other 6. The second person (height 2) has only the 4 in front, so k = 1.

Example 2

Input: people = [[3, 2], [3, 0], [3, 1]]

Output: [[3, 0], [3, 1], [3, 2]]

Everyone has the same height, so each person counts everyone in front of them.

Constraints