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