Problem statement

https://binarysearch.com/problems/Recover-Order-on-Queue-of-People/

Solution 1

Equal to Leetcode 0406. Queue Reconstruction by Height.

Complexity

It is O(n^2) for time and O(n) for space.

Code

class Solution:
    def solve(self, people):
        people = [[x,y,y] for x, y in people]
        
        out = []
        while people:
            ind = people.index(min(people,key=lambda x: (x[2],x[0])))
            out.append(people.pop(ind))
            people = [[x,y,z - (x <= out[-1][0])] for x,y,z in people ]
    
        return [[x,y] for x,y,z in out]

Solution 2

There is better O(n log n) solution as well! The idea is to use sorted list in python to simulate our process.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def solve(self, Q):
        l = len(Q)
        order = [None] * l

        SList = SortedList(range(l))
        for h, c in sorted(Q, key = lambda x: (x[0], -x[1])):
            order[SList[c]] = (h, c)
            SList.pop(c)

        return order