容纳特定人数所需的最少汽车

Question

我进行了一轮编码，问题陈述是这样的

*您有给定数量的朋友和他们汽车的座位容量，现在您需要找到容纳他们所有人所需的最小汽车数量。

例子：

People = [1, 4, 1]
SeatingCapacity = [1, 5, 1]

在这种情况下，我们需要最少的2汽车，因为索引 0 的人数可以使用索引 1 的汽车进行调整。

示例2：

People = [4, 4, 5, 3]
SeatingCapacity = [5, 5, 7, 3]

此案例的答案将是索引 3 人可以容纳到 0、1、2 或 1,2 索引汽车*

我写了这样的代码

People = [1, 4, 1]
SeatingCapacity = [1, 5, 1]

然而，我的代码在很多情况下都失败了，而且还指出了一些性能问题。谁能告诉我我错过了哪些案例？

Answer 1

这可以通过贪心方法来解决。就像下面这样：

people = [1,4,1]
p = sum(people) //6
cars = [1,5,1]
sort(cars, descending) //cars = [5,1,1]
idx = 0
while(p > 0) { p -= cars[idx]; idx += 1 }
answer = idx

处理汽车总容量小于人数的极端情况。

复杂性：sorting cars O(n log n) + while loop O(n) = O(n log n)