मान लीजिए हमारे पास बॉक्स की एक सूची है जहां प्रत्येक पंक्ति दिए गए बॉक्स की ऊंचाई और चौड़ाई को दर्शाती है। हम एक बॉक्स को दूसरे बॉक्स में रख सकते हैं यदि पहला बॉक्स दूसरे से छोटा है (जब इसकी चौड़ाई और ऊंचाई दोनों दूसरे बॉक्स से छोटी हैं), हमें एक बॉक्स के अंदर फिट होने वाले बॉक्स की अधिकतम संख्या ढूंढनी है।
इसलिए, यदि इनपुट इस तरह है
| चौड़ाई | ऊंचाई |
| 12 | 12 |
| 10 | 10 |
| 6 | 6 |
| 5 | 10 |
तो आउटपुट 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 < this_h शून्येतर है, तो
- res := m
- l := m + 1
- अन्यथा,
- r := m - 1
- res + 1 लौटाएं
- मुख्य मेथड से, निम्नलिखित करें:
- मैट्रिक्स को चौड़ाई के आधार पर सॉर्ट करें, यदि चौड़ाई समान है तो ऊंचाई के आधार पर सॉर्ट करें
- n := मैट्रिक्स में आइटम की संख्या
- heights := (n + 1) आकार की सूची और इसे inf से भरें
- heights[0] := -inf
- res := 0
- मैट्रिक्स में प्रत्येक बॉक्स के लिए, करें
- [cur_w, cur_h] := बॉक्स
- index := insert_index(heights, cur_h)
- यदि heights[index] >= cur_h, तो
- heights[index] := cur_h
- res := res और index का अधिकतम
- res लौटाएं
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
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
