Queue Reconstruction by Height

problem at: https://www.leetcode.com/problems/queue-reconstruction-by-height

# Solution

# Greedy

Algorithm:

  • sort people:
    • in the descending order by height
    • among the guys of the same height, in the ascending order by k-values
  • take guys one by one, and place them in the output array at the indexes equal to their k-values.
  • return output array

Basically there are 2 steps. First, we handle the people from tallest (largest h) to shortest b/c the short people don't affect k of tall ones. People w/ lower k are before the higher in result. Then, we keep inserting to kth position the next tallest person.

def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
    res = []
    people.sort(key = lambda elt: (-elt[0], elt[1]))
    for person in people:
        res.insert(person[1], person)
    return res