問題描述

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