โปรแกรมหาจำนวนกล่องสูงสุดที่เราสามารถใส่ลงในกล่องอื่นใน python

สมมติว่าเรามีรายการกล่องที่แต่ละแถวแสดงถึงความสูงและความกว้างของกล่องที่กำหนด เราสามารถใส่กล่องลงในกล่องอื่นได้ถ้ากล่องแรกมีขนาดเล็กกว่ากล่องที่สอง (เมื่อความกว้างและความสูงทั้งสองน้อยกว่ากล่องอื่น) เราต้องหาจำนวนกล่องสูงสุดที่เราจะใส่ลงในกล่องได้

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

จากนั้นผลลัพธ์จะเป็น 3 เนื่องจากเราสามารถใส่กล่อง [6, 6] ภายใน [10, 10] ซึ่งเราสามารถใส่ลงในกล่อง [12, 12] ได้

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

• กำหนดฟังก์ชัน insert_index() นี่จะใช้เวลา arr this_h
• l :=0
• r :=ขนาดของ arr - 1
• res :=0
• ในขณะที่ l <=r ทำ
  • m :=l +(r - l) // 2
  • cur_h :=arr[m]
  • ถ้า cur_h
  • res :=ม
  • l :=m + 1
• มิฉะนั้น
  • r :=m - 1

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

ตัวอย่าง

class Solution:
   def solve(self, matrix):
      matrix = sorted(matrix, key=lambda x: (x[0], -x[1]))
      n = len(matrix)

      heights = [float("inf")] * (n + 1)
      heights[0] = float("-inf")
      res = 0

      for box in matrix:
         cur_w, cur_h = box
         index = self.insert_index(heights, cur_h)

         if heights[index] >= cur_h:
            heights[index] = cur_h
         res = max(res, index)
      return res

   def insert_index(self, arr, this_h):
      l = 0
      r = len(arr) - 1
      res = 0
      while l <= r:
         m = l + (r - l) // 2
         cur_h = arr[m]
         if cur_h < this_h:
            res = m
            l = m + 1
         else:
            r = m - 1
      return res + 1

ob = Solution()
matrix = [
   [12, 12],
   [10, 10],
   [6, 6],
   [5, 10]
]
print(ob.solve(matrix))

อินพุต

matrix = [  
[12, 12],  
[10, 10],  
[6, 6],  
[5, 10] ]

ผลลัพธ์

3