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

在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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程