MediumPro challengePythonJavaScriptTypeScript
Greedy — Queue Reconstruction by Height
AlgorithmsGreedySorting
solve(people) — people[i] = [h, k] means person i is h tall and exactly k
people in front of them in the queue are at least as tall. Rebuild a queue that
satisfies every person and return it as a list of [h, k] pairs. A valid queue is
guaranteed to exist and is unique for the inputs given here.
Greedy idea: handle people from tallest to shortest (taller first; for equal
height, smaller k first) and insert each at index `k`. Shorter people inserted
later never affect the count of the taller people already placed.
Examples
solve([[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]])
→ [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
solve([[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]])
→ [[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]
solve([[1,0]]) → [[1,0]]Sample tests
Test #1Classic example
Input: [[[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]]
Test #2Second classic example
Input: [[[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]]
Test #3One person
Input: [[[1,0]]]
Output: [[1,0]]