Queue Reconstruction - Implementation

Here is the solution:

function reconstructQueue(people)
 sort people by height descending, then k ascending
 result := []
 for each (h, k) in people
 result.insert(at index k, value (h, k))
 return result

Time: $O(n^2)$ due to insertions. Space: $O(n)$.

Example: $[7,0]$ first, then $[7,1]$ at index $1$, then $[6,1]$ at index $1$ (shifts $[7,1]$ right), and so on. Each insertion places the person correctly relative to taller people already present.