โปรแกรมกู้คืนคิวสับคนใน python

สมมติว่าเรามีเมทริกซ์ 2 มิติ โดยแต่ละแถวมีค่าสองค่า [height, count] ซึ่งบ่งชี้ว่าบุคคลนั้นให้ความสูง และมีจำนวน 'นับ' อยู่ข้างหน้าพวกเขาอย่างน้อยก็สูงพอๆ กับพวกเขา ตอนนี้พิจารณาว่ามีการสับเปลี่ยนคิว เราต้องกู้คืนลำดับเดิมของคิว

ดังนั้นหากอินพุตเป็นแบบ

แล้วผลลัพธ์ที่ได้จะเป็น

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:

• N :=จำนวนแถวของเมทริกซ์
• จัดเรียงแถวเมทริกซ์ใหม่ตามความสูงที่เพิ่มขึ้นและจำนวนที่ลดลง
• ans :=ทำรายการขนาด N และเริ่มต้นรายการทั้งหมดเป็นโมฆะ
• สำหรับแต่ละส่วนสูง h และนับ c ในแถวเมทริกซ์ ทำ
  • อุณหภูมิ :=0
  • สำหรับแต่ละดัชนี i และค่าจำนวน ans ทำ
    • ถ้า temp> =c และ num เป็น null แล้ว
      • ans[i] :=[h, c]
      • ออกมาจากวงจร
    • ถ้า num เป็น null หรือ num[0]>=h แล้ว
      • อุณหภูมิ :=อุณหภูมิ + 1
• คืนสินค้า

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:

ตัวอย่าง

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

อินพุต

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

ผลลัพธ์

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