程序以找到我们可以放入python另一个盒子中的盒子的最大数量

  • Z时代
  • 2024-01-10
  • 分类：综合

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

所以，如果输入像

宽度
高度
12
12
10
10
6
6
5
10

那么输出将是3，因为我们可以将[10，10]内的框[6，6]放进[12，12]框内。

为了解决这个问题，我们将遵循以下步骤-

  • 定义一个函数insert_index()。这将需要arr，this_h

  • l：= 0

  • r：= arr的大小-1

  • res：= 0

  • 当l <= r时

    • r：= m-1

    • 分辨率：=米

    • l：= m +1

    • m：= l +(r-l)// 2

    • cur_h：= arr [m]

    • 如果cur_h <this_h为非零，则

    • 除此以外，

    • 返回res + 1

    • 在主要方法中，执行以下操作：

    • 如果宽度相同，则根据宽度对矩阵进行排序；如果高度相同，则对它们进行排序

    • n：=矩阵中的项目数

    • heights：=大小列表（n + 1）并用inf填充

    • 高度[0]：= -inf

    • res：= 0

    • 对于矩阵中的每个框，执行

      • 高度[索引]：= cur_h

      • [cur_w，cur_h]：=框

      • 索引：= insert_index(heights,cur_h)

      • 如果heights [index]> = cur_h，则

      • res：= res和index的最大值

    • 返回资源

    让我们看下面的实现以更好地理解-

    例 

    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

    以上是 程序以找到我们可以放入python另一个盒子中的盒子的最大数量 的全部内容， 来源链接： utcz.com/z/326427.html

    回到顶部