# Leetcode 406 - Queue reconstructing by height

Note:

• How to be greedy?
• Local optima: Meet the rules on every insertion.
• Global optima: Every element meets the conditions.
• When it comes to 2D array. Usually we need to sort by one dimension, then another.
• For [i, j], because j depends on taller heights, we need to sort people first by i in descending order first.
• Create an empty array, iterate from left to right while inserting. Because the existing elements in our result already have bigger i (height), it means j is the index that we want to insert to.

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 greater than or equal to hi.

Reconstruct and return the queue that is represented by the input array people. The returned queue should be formatted as an array queue, where queue[j] = [hj, kj] is the attributes of the jth person in the queue (queue[0] is the person at the front of the queue).

Example