Chương trình khôi phục hàng đợi người bị xáo trộn bằng Python

Cho ma trận mỗi hàng [height, count]: người có chiều cao height, có count người trước đó cao hơn hoặc bằng. Hàng đợi bị xáo trộn, khôi phục thứ tự gốc.

Ví dụ: [[2,2],[4,0],[5,0]] → [[4,0],[5,0],[2,2]].

Giải thuật

• Sắp xếp người: tăng dần chiều cao, giảm dần count.
• Khởi tạo mảng kết quả ans kích thước N toàn None.
• Duyệt người theo thứ tự đã sắp: chèn vào vị trí đầu tiên trong ans mà trước đó đã có đủ count người cao hơn hoặc bằng (đếm ô trống hoặc người cao hơn).

Ví dụ minh họa

class Solution:
    def solve(self, matrix):
        N = len(matrix)
        matrix.sort(key=lambda x: [x[0], -x[1]])
        ans = [None] * N
        for h, c in matrix:
            temp = 0
            for i, num in enumerate(ans):
                if temp >= c and num is None:
                    ans[i] = [h, c]
                    break
                if num is None or num[0] >= h:
                    temp += 1
        return ans

ob = Solution()
matrix = [[2,2],[4,0],[5,0]]
print(ob.solve(matrix))

Đầu vào

[[2,2],[4,0],[5,0]]

Đầu ra

[[4,0], [5,0], [2,2]]