在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