程序以找到我们可以放入python另一个盒子中的盒子的最大数量
假设我们有一个盒子列表,其中每一行代表给定盒子的高度和宽度。如果第一个盒子小于第二个盒子(当它的宽度和高度都小于另一个盒子时),我们可以将一个盒子放到另一个盒子中,我们必须找到一个盒子可以容纳的最大盒子数量。
所以,如果输入像
那么输出将是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