Chương trình tìm số hộp tối đa mà chúng ta có thể vừa với các hộp khác trong python

Giả sử chúng ta có một danh sách các hộp trong đó mỗi hàng đại diện cho chiều cao và chiều rộng của các hộp đã cho. Chúng ta có thể đặt một hộp vào một hộp khác nếu hộp thứ nhất nhỏ hơn hộp thứ hai (khi cả chiều rộng và chiều cao của nó nhỏ hơn hộp kia), chúng ta phải tìm số hộp tối đa mà chúng ta có thể xếp được vào một hộp.

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

thì đầu ra sẽ là 3, vì chúng ta có thể đặt vừa hộp [6, 6] bên trong [10, 10] mà chúng ta có thể đặt vào hộp [12, 12].

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

• Xác định một hàm insert_index (). Điều này sẽ mất arr, this_h
• l:=0
• r:=kích thước của arr - 1
• res:=0
• trong khi l <=r, thực hiện
  • m:=l + (r - l) // 2
  • cur_h:=arr [m]
  • nếu cur_h
  • res:=m
  • l:=m + 1
• nếu không,
  • r:=m - 1

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

Đầu vào

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

Đầu ra

3