334. Queue Reconstruction by Height
A group of n people once stood in a queue, and then the queue got shuffled. Each person i remembers only two numbers: their height hᵢ, and kᵢ — how many of the people standing anywhere in front of them were at least as tall as they were (height ≥ hᵢ).
You receive the pairs people[i] = [hᵢ, kᵢ] in arbitrary order. Rebuild the original queue: return the same pairs arranged front to back so that every person's k is consistent with who ends up ahead of them.
The input is always consistent, and a consistent input pins down exactly one possible queue — return that unique arrangement.
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]]
Explanation: Reading the answer front to back: [5,0] has nobody ahead; [7,0] has one person ahead but they're shorter; [5,2] sees the 5 and the 7 ahead, both ≥ 5; [6,1] sees only the 7; [4,4] sees all four earlier people; [7,1] sees exactly one person ≥ 7, the other 7.
Example 2:
Input: people = [[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]]
Explanation: Every person's k matches: e.g. [2,2] stands behind the 4 and the 5 (both ≥ 2), and [6,0] stands last with nobody ≥ 6 ahead.
Constraints:
- 1 ≤ n ≤ 2000
- 0 ≤ hᵢ ≤ 10⁶
- 0 ≤ kᵢ < n
- The input is consistent: at least one queue produces these pairs, and that queue is unique.
Hints:
Shorter people are invisible to taller people's counts. If you deal with people from tallest to shortest, everyone already placed is ≥ the person you're placing — so their k counts *exactly* the placed people who must stand in front of them.
Sort by height descending, breaking ties by k ascending, and insert each person at index k of the answer built so far. Later insertions are shorter, so sliding them in never breaks anyone's count.
For O(n log n): flip it around — place shortest first (ties: larger k first) into the (k+1)-th still-EMPTY slot, using a Fenwick tree to find that slot; the empty slots are exactly where the taller people will later stand.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
Expected output: [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]