Skip to content

3074. Apple Redistribution into Boxes 👍

  • Time: $O(\texttt{sort})$
  • Space: $O(\texttt{sort})$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
 public:
  int minimumBoxes(vector<int>& apple, vector<int>& capacity) {
    const int appleSum = accumulate(apple.begin(), apple.end(), 0);
    int capacitySum = 0;

    ranges::sort(capacity, greater<>());

    for (int i = 0; i < capacity.size(); ++i) {
      capacitySum += capacity[i];
      if (capacitySum >= appleSum)
        return i + 1;
    }

    return capacity.size();
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
  public int minimumBoxes(int[] apple, int[] capacity) {
    final int appleSum = Arrays.stream(apple).sum();
    int capacitySum = 0;

    Arrays.sort(capacity);

    for (int i = 0; i < capacity.length; ++i) {
      capacitySum += capacity[capacity.length - 1 - i];
      if (capacitySum >= appleSum)
        return i + 1;
    }

    return capacity.length;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
  def minimumBoxes(self, apple: list[int], capacity: list[int]) -> int:
    appleSum = sum(apple)
    capacitySum = 0

    for i, c in enumerate(sorted(capacity, reverse=True)):
      capacitySum += c
      if capacitySum >= appleSum:
        return i + 1

    return len(capacity)