Queue Reconstruction by Height

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 >= hi. Reconstruct and return the queue that is represented by the input array.

30:00

Queue Reconstruction by Height

medium

Topics

Companies

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 >= hi. Reconstruct and return the queue that is represented by the input array.

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]]

Constraints:

$1 \leq \text{people.length} \leq 2000$
$0 \leq h_i \leq 10^6$
$0 \leq k_i < \text{people.length}$
It is guaranteed that a valid queue can be reconstructed.

Input

arr ={"people":[[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]}

Initial queue with 6 people

Original Input

h=7

k=0

h=4

k=4

h=7

k=1

h=5

k=0

h=6

k=1

h=5

k=2

Result Queue

(empty)

h = height, k = people in front with height >= h

Variables

No variables to display

DepthFunction Call

Stack empty

0/8