406. Queue Reconstruction by Height

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers(h, k), wherehis the height of the person andkis the number of people in front of this person who have a height greater than or equal toh. 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]]

Thoughts:

1. Sort the h in descending order and k in ascending order.

2. Traverse the sorted list and insert the current person into kth position of new list.

Code T: O(n^2) S:O(n)

class Solution(object):
    def reconstructQueue(self, people):
        """
        :type people: List[List[int]]
        :rtype: List[List[int]]
        """
        people.sort(key = lambda x: [-x[0], x[1]])
        result = []
        for [h, k] in people:
            result.insert(k, [h,k])
        return result

more explicit way: first group the height, then sort in each group, then insert into the final list:

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

        # sort the h, and then sort the k and insert into kth postiion in new list
        peopledict, height, res = {}, [], [] 
        for i in range(len(people)):
            p = people[i]
            if p[0] not in peopledict:
                peopledict[p[0]] = [(p[1], i)]
                height+= p[0],
            else:
                peopledict[p[0]] += (p[1], i),

        height.sort(reverse=True)
        for h in height:
            peopledict[h].sort()
            for k, i in peopledict[h]:
                res.insert(k, people[i])
        return res

the first solution is from djrochford and the second is from YJL1228 in this post