Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Apples from one pack may be split between boxes, so only the total number of apples matters. For any chosen number of boxes, the largest capacities provide the most space. Taking them first therefore reaches sufficient capacity with as few boxes as possible.

Approach

Sum all pack sizes and sort box capacities in descending order. Process boxes from largest to smallest, subtracting each capacity from the number of apples still needing space. As soon as the current box can hold all remaining apples, return the number of boxes processed, including that box.

No smaller collection can work: before this step, even the largest available capacities for that smaller count were insufficient. The problem guarantees enough total capacity, so the scan reaches a successful return.

class Solution:
    def minimumBoxes(self, apple: List[int], capacity: List[int]) -> int:
        apples = sum(apple)
        capacity.sort(reverse = True)

        for i, c in enumerate(capacity):
            if apples > c:
                apples -= c
            else:
                return i + 1

Complexity analysis

Let a = apple.length and b = capacity.length. Time: O(a + b log b). Auxiliary space: O(b) in the worst case for built-in sorting.