अधिकतम संख्या में बॉक्स खोजने के लिए प्रोग्राम जिसे हम अजगर में किसी अन्य बॉक्स के अंदर फिट कर सकते हैं

मान लीजिए हमारे पास बक्से की एक सूची है जहां प्रत्येक पंक्ति दिए गए बक्से की ऊंचाई और चौड़ाई का प्रतिनिधित्व करती है। हम एक बॉक्स को दूसरे बॉक्स में रख सकते हैं यदि पहला बॉक्स दूसरे बॉक्स से छोटा है (जब इसकी चौड़ाई और ऊंचाई दोनों दूसरे बॉक्स से छोटी हों), तो हमें बॉक्स में फिट होने वाले बॉक्स की अधिकतम संख्या ज्ञात करनी होगी।

तो, अगर इनपुट पसंद है

तब आउटपुट 3 होगा, क्योंकि हम [10, 10] के अंदर [6, 6] बॉक्स को फिट कर सकते हैं, जिसे हमें [12, 12] बॉक्स में रखा जा सकता है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक फ़ंक्शन को परिभाषित करें insert_index() । यह गिरफ्तार होगा, this_h
• एल :=0
• r :=गिरफ्तारी का आकार - 1
• res :=0
• जबकि l <=r, करते हैं
  • m :=l +(r - l) // 2
  • cur_h :=arr[m]
  • अगर cur_h
  • res :=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