在Python中查找可以容纳在另一个盒子中的最大盒子数量的程序

假设我们有一个盒子列表，其中每一行表示给定盒子的高度和宽度。如果第一个盒子比第二个盒子小（当宽度和高度都小于另一个盒子时），我们可以将一个盒子放在另一个盒子中。我们必须找到可以放入盒子中的最大盒子数量。

因此，如果输入为

Width	Height
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
• while 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]：= box
  • index ：= insert_index（heights，cur_h）
  • 如果heights[index] >= cur_h，则
    • heights[index] := cur_h
  • res ：= res和索引的最大值
• 返回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