আমরা পাইথনে অন্য বাক্সের মধ্যে ফিট করতে পারি এমন সর্বাধিক সংখ্যক বাক্স খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের কাছে বাক্সগুলির একটি তালিকা রয়েছে যেখানে প্রতিটি সারি প্রদত্ত বাক্সগুলির উচ্চতা এবং প্রস্থকে প্রতিনিধিত্ব করে। প্রথম বক্সটি দ্বিতীয়টির চেয়ে ছোট হলে আমরা অন্য একটি বাক্সে একটি বাক্স রাখতে পারি (যখন এটির প্রস্থ এবং উচ্চতা উভয়ই অন্য বক্সের চেয়ে ছোট), আমাদের একটি বাক্সে ফিট করা সর্বোচ্চ সংখ্যক বাক্স খুঁজে বের করতে হবে৷

সুতরাং, যদি ইনপুট মত হয়

তাহলে আউটপুট হবে 3, যেহেতু আমরা বক্সটি [6, 6] ভিতরে [10, 10] ফিট করতে পারি যা আমাদের [12, 12] বক্সে রাখা যেতে পারে।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন সংজ্ঞায়িত করুন insert_index()। এটি arr, this_h
লাগবে
• l :=0
• r :=arr এর আকার - 1
• res :=0
• যখন l <=r, do
  • m :=l +(r - l) // 2
  • cur_h :=arr[m]
  • যদি cur_h
  • res :=m
  • 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