Easy understanding Python Solution, using cmp


  • 0
    D

    First constructing new class queue aims to replace the two-dimensional list people when sorting afterwards.

    Override cmp, because we want the one has the highest height to come out first, if two or more people have same the highest height, we want the one has the lowest k value to come out first. In this way, we can simply insert the person in queue based on their k value one by one.

    So the process would be:
    Input:
    [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

    After Sorted:
    [[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]

    Insert based on k to ans one by one (if k is higher or equal to ans current length, just append it to ans's end):
    [[7,0]]
    [[7,0], [7,1]]
    [[7,0], [6,1], [7,1]]
    [[5,0], [7,0], [6,1], [7,1]]
    [[5,0], [7,0], [5,2], [6,1], [7,1]]
    [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

    class queue:
        def __init__(self, height, k):
            self.h = height
            self.k = k
        def __cmp__(self, other):
            if cmp(self.h, other.h) != 0:
                return cmp(self.h, other.h)
            else:
                return cmp(other.k, self.k)
        
    class Solution(object):
        def reconstructQueue(self, people):
            """
            :type people: List[List[int]]
            :rtype: List[List[int]]
            """
            q = []
            for person in people:
                q.append(queue(person[0], person[1]))
            
            peopleQueue = sorted(q, reverse=True)
            
            ans = []
            for person in peopleQueue:
                if person.k >= len(ans):
                    ans.append([person.h, person.k])
                else:
                    ans.insert(person.k, [person.h, person.k])
            
            return ans
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.