DSA problem
Apple Redistribution into Boxes
You are given an array apple representing the number of apples in each of n packs, and an array capacity representing the capacities of m boxes. Your goal is to redistribute the apples from all n packs into the fewest possible boxes, and return that minimum number. Each apple must end up in some box and you may not exceed any box's capacity.
The setup is essentially a bin-packing question, which is NP-hard in general, but the simplification here is that apples are interchangeable — we only care about counts, not which apple goes where. That removes all combinatorial structure and turns the question into: pick the fewest boxes whose total capacity is at least the total number of apples.
Once we accept that framing, the optimal strategy is unmistakable. Sort the box capacities in descending order and add them one by one until the running sum covers the total apple count. Each step buys us as much capacity as currently possible, so no other choice could finish in fewer boxes — an exchange argument shows any optimal solution can be swapped to favor larger boxes without using more of them.
Time complexity is dominated by the sort at O(m log m), plus a linear scan to find the cutoff. Space is O(1) beyond the input (or O(m) if a sort copy is needed). The pattern is a textbook greedy: define a global quantity to cover, then meet it as fast as possible with the most powerful resources first.
Examples
apple = [1,3,2], capacity = [4,3,1,5,2]2apple = [5,5,5], capacity = [2,4,2,7]4apple = [10], capacity = [3,5,8,12]1Constraints
- 1 <= n == apple.length <= 50
- 1 <= m == capacity.length <= 50
- 1 <= apple[i], capacity[i] <= 50
- The input is generated such that it is possible to redistribute apples into boxes.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.