The Queue Reconstruction by Height problem gives you people with (height, k) pairs where k is the number of taller-or-equal people in front of them. Reconstruct the queue such that all k values are satisfied. This Queue Reconstruction by Height coding problem uses a greedy sort-then-insert approach. The array, sorting, binary indexed tree, and segment tree interview pattern is demonstrated.
Meta, Amazon, and Google ask this because the greedy insight — sort by height descending, then insert each person at their k position — is non-obvious. The correctness relies on the fact that shorter people don't affect the relative count of taller people.
Sort + insert at k position. Sort by height descending (equal heights by k ascending). For each person, insert at index k in the result array. Taller people are placed first; inserting shorter people at position k only counts already-placed (taller) people before them.
people=[[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]. Sort: [[7,0],[7,1],[6,1],[5,0],[5,2],[4,4]].
Queue Reconstruction by Height is a landmark greedy problem. The proof of correctness: since we process tallest first, inserting at position k places the person among exactly k taller people already in the queue. Shorter people inserted later don't disturb the k count. Practice similar "greedy with insertion" problems. For large n, use BIT for O(log n) insert operations instead of O(n) list insert.
