406. Queue Reconstruction by Hei

问题描述

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

思路

First, sort the list people, so that people with lower k stand in front of those with higher k. Also, people with greater h will stand in front of people with smaller h.
对于 h相同的人, k 小的人，会站在 k大的人的后面。 并且排序过后h值高的人站在前面
Then, create an empty list.
在排序过后，每个k值表示这个人要站的位置。
因为h值在减小，在某个人前面插入别的人，并不会影响到k值。

    def reconstructQueue(self, people):
        """
        :type people: List[List[int]]
        :rtype: List[List[int]]
        """
        sortByK = sorted(people, key=lambda s: s[1])
        sortByH = sorted(sortByK, key=lambda s: s[0], reverse=True)
        ans = []
        for i in sortByH:
            ans.insert(i[1], i)
        return ans