Apple Redistribution into Boxes

main.md

Question

Approach

First, I compute the total number of apples across all packs. To minimize the number of boxes, I should always pick the largest-capacity boxes first, because bigger boxes cover more apples with fewer boxes.

So I:

• Sum all apples → need
• Sort capacity in descending order
• Keep adding box capacities until the running sum ≥ need
• Return how many boxes were used

Implementation

class Solution:
    def minimumBoxes(self, apple: List[int], capacity: List[int]) -> int:
        need = sum(apple)
        capacity.sort(reverse=True)
        
        total = 0
        boxes = 0
        
        for c in capacity:
            total += c
            boxes += 1
            if total >= need:
                return boxes

Complexities

• Time: O(n logn)
• Space: O(n)