Problem Statement

You are given an array apple of size n, where the apple[i] represents the number of apples in i^th pack. You are also given an array capacity of size m, where capacity[j] is a number of apples that can be stored in the j^th box.

Return the minimum number of boxes you need to use to put these all n packs of apples into boxes.

Note: You are allowed to distribute apples from the same pack into different boxes.

Examples

Example 1:

• Input: apple = [2, 3, 1], capacity = [4, 2, 5, 1]
• Expected Output: 2
• Explanation: Box 1 can take apples from packs 1 and 2 partially (totaling 5 apples), and Box 2 can take the rest of 2 apples.

Example 2:

• Input: apple = [4, 5, 6], capacity = [5, 10]
• Expected Output: 2
• Explanation: Box 1 can take apples from packs 1 and 2 partially (totaling 5 apples), and Box 2 can take the rest of pack 2 and all of pack 3 apples.

Example 3:

• Input: apple = [1, 2, 5, 6], capacity = [2, 3, 7, 4, 5, 2, 4]
• Expected Output: 3
• Explanation: We can use boxes of size 7, 5, and 2 to pack all apples in boxes.

Constraints:

• 1 <= n == apple.length <= 50
• 1 <= m == capacity.length <= 50
• 1 <= apple[i], capacity[i] <= 50
• The input is generated such that it's possible to redistribute packs of apples into boxes.

Solution

To solve this problem, we use sorting approach. The core idea is to efficiently distribute apples into boxes by always attempting to fill the largest capacity box available. This approach is believed to be effective because filling the largest boxes first reduces the number of boxes needed faster, akin to fitting the largest pieces into a puzzle first.

We will start by sorting the capacity array in descending order so we can always access the largest box first. The apples from each pack will be allocated starting from the box with the highest capacity, using a priority queue to manage and update the available space in the boxes quickly.

Step-by-step Algorithm

• Step 1: Sort the boxCapacities array in ascending order to strategically use the largest boxes last.
• Step 2: Initialize a variable totalApples to accumulate the total number of apples that need to be boxed.
• Step 3: Iterate over the apples array to calculate totalApples by adding up all the apples in the packs.
• Step 4: Initialize an index i to the last position of the boxCapacities array to start using boxes from the largest to the smallest.
• Step 5: Use a while loop to distribute apples into boxes:
  • Step 5a: Subtract the capacity of the box at index i from totalApples.
  • Step 5b: Decrement the index i to move to the next largest box.
  • Step 5c: Continue this process until all apples are distributed (totalApples <= 0) or there are no more boxes (i < 0).
• Step 6: Calculate the number of boxes used, which is the difference between the total number of boxes and the boxes that were not used.

Algorithm Walkthrough

Let's consider the input: apple = [1, 2, 5, 6], capacity = [2, 3, 7, 4, 5, 2, 4]

• Step 1: Original boxCapacities = [2, 3, 7, 4, 5, 2, 4]. Sorted boxCapacities = [2, 2, 3, 4, 4, 5, 7]

• Step 2: Initialize totalApples = 0.

• Step 3: Process apples:

  • Adding apples from pack 1: totalApples = 1
  • Adding apples from pack 2: totalApples = 3
  • Adding apples from pack 3: totalApples = 8
  • Adding apples from pack 4: totalApples = 14

• Step 4: Initialize index i = 6 (last index of boxCapacities).

• Step 5: Begin distributing apples:

  • Step 5a: Using box with capacity 7: totalApples = 14 - 7 = 7
  • Step 5b: Decrement i = 5
  • Step 5a: Using box with capacity 5: totalApples = 7 - 5 = 2
  • Step 5b: Decrement i = 4
  • Step 5a: Using box with capacity 4: totalApples = 2 - 4 = -2 (all apples distributed, and extra capacity remains)

• Step 6: Calculate boxes used:

  • Initially, i = 6
  • Final i = 4
  • Boxes used = 6 - 4 + 1 = 3