Queue Reconstruction by Height

首先这肯定不是一个贪心算法的问题，无论从描述和要求各方面都能看出这是一个自定义排序的问题，这里关键问题在于找到这个内在的排序规律，首先把队列按照从高到矮，index从小到大的混合方式排序，接着我们就可以对各个元素逐个进行类插入排序的处理了，因为我们每次处理到当前的元素时，其左侧的元素身高肯定大于等于它，所以我们可以直接找到它的index对应位置插入进去即可，大致的思路就是这样去处理，下面是比较清楚的代码，另外注意这里的排序方式是身高从大到小，但是index还是从小到大的，另外这里的排序是in-place的

class Solution(object):
    def reconstructQueue(self, people):
        """
        :type people: List[List[int]]
        :rtype: List[List[int]]
        """
        if not people:
            return []

        def comparator(A, B):
            if A[0] != B[0]:
                return B[0] - A[0]
            return A[1] - B[1]
        people.sort(cmp=comparator)
        startIndex = 0
        n = len(people)
        maxHeight = people[0][0]

        while startIndex < n and people[startIndex][0] == maxHeight:
            startIndex += 1

        for i in xrange(startIndex, n):
            cur = i
            while cur >= 0 and people[cur][1] < cur:
                people[cur], people[cur - 1] = people[cur - 1], people[cur]
                cur -= 1 

        return people

如果没有in-place限制，代码可以放很短

class Solution(object):
    def reconstructQueue(self, people):
        """
        :type people: List[List[int]]
        :rtype: List[List[int]]
        """
        people.sort(cmp=lambda x, y: cmp(y[0], x[0]) if x[0] != y[0] else cmp(x[1], y[1]))
        result = []
        for person in people:
            result.insert(person[1], person)
        return result