Question

3074. 重新分装苹果

English Version

题目描述

给你一个长度为 n 的数组 apple 和另一个长度为 m 的数组 capacity 。

一共有 n 个包裹，其中第 i 个包裹中装着 apple[i] 个苹果。同时，还有 m 个箱子，第 i 个箱子的容量为 capacity[i] 个苹果。

请你选择一些箱子来将这 n 个包裹中的苹果重新分装到箱子中，返回你需要选择的箱子的 最小 数量。

注意，同一个包裹中的苹果可以分装到不同的箱子中。

 

示例 1：

输入：apple = [1,3,2], capacity = [4,3,1,5,2]
输出：2
解释：使用容量为 4 和 5 的箱子。
总容量大于或等于苹果的总数，所以可以完成重新分装。

示例 2：

输入：apple = [5,5,5], capacity = [2,4,2,7]
输出：4
解释：需要使用所有箱子。

 

提示：

• 1 <= n == apple.length <= 50
• 1 <= m == capacity.length <= 50
• 1 <= apple[i], capacity[i] <= 50
• 输入数据保证可以将包裹中的苹果重新分装到箱子中。

解法

方法一：贪心 + 排序

为了使得需要的箱子数量尽可能少，我们应该优先使用容量大的箱子。因此，我们可以对箱子按照容量从大到小排序，然后依次使用箱子，直到所有的苹果都被分装完，返回此时使用的箱子数量。

时间复杂度 $O(m \times \log m + n)$，空间复杂度 $O(\log m)$。其中 $m$ 和 $n$ 分别是数组 capacity 和 apple 的长度。

class Solution:
  def minimumBoxes(self, apple: List[int], capacity: List[int]) -> int:
    capacity.sort(reverse=True)
    s = sum(apple)
    for i, c in enumerate(capacity, 1):
      s -= c
      if s <= 0:
        return i

class Solution {
  public int minimumBoxes(int[] apple, int[] capacity) {
    Arrays.sort(capacity);
    int s = 0;
    for (int x : apple) {
      s += x;
    }
    for (int i = 1, n = capacity.length;; ++i) {
      s -= capacity[n - i];
      if (s <= 0) {
        return i;
      }
    }
  }
}

class Solution {
public:
  int minimumBoxes(vector<int>& apple, vector<int>& capacity) {
    sort(capacity.rbegin(), capacity.rend());
    int s = accumulate(apple.begin(), apple.end(), 0);
    for (int i = 1;; ++i) {
      s -= capacity[i - 1];
      if (s <= 0) {
        return i;
      }
    }
  }
};

func minimumBoxes(apple []int, capacity []int) int {
  sort.Ints(capacity)
  s := 0
  for _, x := range apple {
    s += x
  }
  for i := 1; ; i++ {
    s -= capacity[len(capacity)-i]
    if s <= 0 {
      return i
    }
  }
}

function minimumBoxes(apple: number[], capacity: number[]): number {
  capacity.sort((a, b) => b - a);
  let s = apple.reduce((acc, cur) => acc + cur, 0);
  for (let i = 1; ; ++i) {
    s -= capacity[i - 1];
    if (s <= 0) {
      return i;
    }
  }
}