পাইথনে বক্স অন্য বক্সের ভিতরে ফিট করার সর্বোচ্চ সংখ্যা বের করার প্রোগ্রাম

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

তাই, ইনপুট যদি নিচের টেবিল হয়, তবে আউটপুট হবে ৩, কারণ [6, 6] বক্সটি [10, 10]-এর ভিতরে ফিট করা যায়, যা আবার [12, 12] বক্সের ভিতরে ফিট করা যায়।

Width	Height
12	12
10	10
6	6
5	10

সমাধানের ধাপগুলো:

insert_index() ফাংশন ডিফাইন করুন। এটি arr, this_h নিবে
- l := 0, r := len(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
- প্রতিটি box ইন matrix এর জন্য, করুন
  - [cur_w, cur_h] := box
  - index := insert_index(heights, cur_h)
  - যদি heights[index] >= cur_h, তবে
    - heights[index] := cur_h
  - res := max(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]]