Apple Redistribution into Boxes
Last Updated: March 29, 2026
Understanding the Problem
We have some packs of apples and some boxes. Each pack has a certain number of apples, and each box can hold a certain number of apples. We want to use as few boxes as possible to fit all the apples.
The key detail is that apples from the same pack can be split across different boxes. This means we don't need to worry about fitting individual packs into individual boxes. We just need the total capacity of our chosen boxes to be at least the total number of apples.
So the problem reduces to: find the minimum number of boxes whose combined capacity is at least the total apple count. To minimize the number of boxes, we should pick the largest boxes first. That's the greedy insight.
Key Constraints:
1 <= n, m <= 50→ Both arrays are tiny, at most 50 elements. Even O(n^3) or O(n^2) are more than fast enough. Sorting is trivially efficient here.1 <= apple[i], capacity[j] <= 50→ Values are small positive integers. No overflow concerns, no negative numbers to handle.- The input guarantees a valid solution exists, so we never need to return -1 or handle the impossible case.
Approach 1: Brute Force (Check All Subsets)
Intuition
The most direct way to find the minimum number of boxes: try every possible subset of boxes, check if the subset's total capacity is enough, and return the smallest valid subset size.
This is what you'd do if you were thinking purely in terms of "which combination of boxes works?" For each subset of size k (starting from k = 1), check if any subset of that size has enough capacity. The first k where we find a valid subset is the answer.
Algorithm
- Compute the total number of apples across all packs.
- Try all subsets of the
capacityarray, starting from the smallest subsets. - For each subset, sum the capacities.
- If the sum is at least the total apples, return the subset size.
Code
- Time Complexity: O(2^m). In the worst case, we examine all subsets of the capacity array. For m boxes, there are 2^m subsets.
- Space Complexity: O(m). The recursion depth is at most m, so the call stack uses O(m) space.
The brute force tries every combination of boxes. But if we want to minimize the count, we should always pick the biggest boxes first, since each large box gets us closer to the target faster. What if we just sorted the boxes by size and greedily picked from the top?
Approach 2: Greedy with Sorting (Optimal)
Intuition
Since apples can be split freely across boxes, the only thing that matters is the total capacity of the boxes we choose. We want to reach the total apple count using as few boxes as possible.
To minimize the number of boxes, we should always pick the box with the largest remaining capacity. This is a classic greedy choice: at each step, take the option that makes the most progress toward our goal. There's no reason to pick a smaller box when a larger one is available, because the larger box gets us closer to the target with fewer selections.
So the approach is simple: sort the capacities in descending order, then keep adding boxes until the cumulative capacity meets or exceeds the total apples.
The greedy choice is provably optimal here. Suppose there's an optimal solution that doesn't include the largest box. We could swap out any box in that solution for the largest box, and the total capacity would only increase (or stay the same). So including the largest box is never worse than excluding it. By induction, always picking the next-largest box gives us the minimum count.
This is a classic "greedy exchange argument." For any solution that skips a larger box in favor of a smaller one, we can swap them and get an equal or better result.
Algorithm
- Compute the total number of apples by summing the
applearray. - Sort the
capacityarray in descending order. - Initialize a running sum of capacity to 0.
- Iterate through the sorted capacities, adding each to the running sum.
- As soon as the running sum reaches or exceeds the total apples, return the number of boxes used.
Example Walkthrough
Code
- Time Complexity: O(n + m log m). Summing the apple array takes O(n). Sorting the capacity array takes O(m log m). The greedy scan is O(m).
- Space Complexity: O(1). We sort in-place and use only a few variables.