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.

Note:
The number of people is less than 1,100.

Example

Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

第一眼看到还以为和发射炮的那个典型贪心一样……

图样图森破

第二个k表示的是前面h比当前h大于或者等于的个数

无知的我想到根据h,k的大小拓扑排序

但是连顺序都排反了

讲真看了题解我也想不通是怎么想到答案的

做法：

先排序，h从大往小,k从小往大

依次把每个对象放到k的位置上，如果k有数了，就把原来的往后串

一定会保证正确，以为插入的过程不会影响已经排好的性质

注意 pop insert的用法

里面的自定义函数不能放到那个函数外面，python会提示找不到

sort的自定义可以key排序  可以cmp排序

注意两个函数的写法

return cmp(p2[1],p1[1]) if p1[0]==p2[0] else cmp(p1[0],p2[0])
简直不能更别扭

还有就是for循环删除要防止越界



class Solution(object):
    
    def reconstructQueue(self, people):
        """
        :type people: List[List[int]]
        :rtype: List[List[int]]
        """
        def my_key(pp):
            return -pp[0],pp[1]#表示按第一个键降序 第二个键升序
        people.sort(key=my_key)
        for i in range(len(people)):
            if i>=len(people):
                break
            if(people[i][1]==i):
                continue
            tmp=people[i]
            people.pop(i)
            people.insert(tmp[1],tmp)
        return people


class Solution(object):
    
    def reconstructQueue(self, people):
        """
        :type people: List[List[int]]
        :rtype: List[List[int]]
        """
        def my_cmp(p1,p2):
            return cmp(p2[1],p1[1]) if p1[0]==p2[0] else cmp(p1[0],p2[0])
        people.sort(cmp=my_cmp,reverse=True)
        for i in range(len(people)):
            if i>=len(people):
                break
            if(people[i][1]==i):
                continue
            tmp=people[i]
            people.pop(i)
            people.insert(tmp[1],tmp)
        return people