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

Giả sử chúng ta có một ma trận 2D trong đó mỗi hàng chứa hai giá trị [chiều cao, số lượng] những giá trị này cho biết người đó đã cho biết chiều cao và có 'số lượng' người phía trước họ cao ít nhất bằng họ. Bây giờ coi như hàng đợi này đã bị xáo trộn, chúng ta phải khôi phục thứ tự ban đầu của hàng đợi.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:

• N:=số hàng của ma trận
• sắp xếp lại các hàng trong ma trận dựa trên việc tăng chiều cao và giảm số lượng
• ans:=tạo một danh sách có kích thước N và ban đầu tất cả các mục nhập đều rỗng
• đối với mỗi chiều cao h và đếm c trong hàng ma trận, thực hiện
  • tạm thời:=0
  • đối với mỗi chỉ mục i và giá trị num ans, thực hiện
    • nếu temp> =c và num là null, thì
      • ans [i]:=[h, c]
      • ra khỏi vòng lặp
    • nếu num là null hoặc num [0]> =h, thì
      • temp:=temp + 1
• trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn:

Ví dụ

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]]