有很多个尺寸不一的红包,以数组的形式给出,其中redPockets[i]= [w, h],表示这个红包的宽度和长度。 当—个红包的宽度和长度比另一个红包大时,就可以将小的红包放入大的红包之中,组成一个套娃红包。 请计算出在给出的红包中,最多能用多少个红包组合成一个套娃红包。
时间: 2023-03-25 14:02:17 浏览: 126
数组中重复的数字_
5星 · 资源好评率100%
我可以回答这个问题。这个问题可以使用贪心算法来解决。首先,将所有红包按照宽度从小到大排序,如果宽度相同,则按照长度从小到大排序。然后,从小到大遍历每个红包,对于每个红包,找到能够放下它的最大的红包,将它放入这个红包中。如果找不到这样的红包,则这个红包不能放入任何一个套娃红包中。最后,统计能够放入套娃红包中的红包数量即可。
阅读全文