- How to be greedy?
Local optima: Meet the rules on every insertion.
Global optima: Every element meets the conditions.
- When it comes to
2Darray. Usually we need to sort by one dimension, then another.
[i, j], because
jdepends on taller heights, we need to sort
- Create an empty array, iterate from left to right while inserting. Because the existing elements in our
resultalready have bigger
i(height), it means
indexthat 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 is the person at the front of the queue).
Input: people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]