Problem Statement in English

You’re given two integer arrays apple and capacity, where apple[i] represents the number of apples in the $i^{th}$ pack, and $capacity[i]$ represents the maximum number of apples that can be placed in the $i^{th}$ box after redistribution.

Return the minimum number of boxes required to redistribute all the apples such that no box exceeds its capacity.

You’re allowed to redistribute apples from any pack to any box, but you cannot exceed the capacity of any box.

Approach

All we really need to do is keep picking the biggest boxes first, with as many apples as it can take. Since we’re allowed to unpack and repack apples as we like, we don’t need to worry about which apples go into which boxes.

Solution in Python


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

        res = 0

        for c in capacity:
            t -= c
            res += 1
            if t <= 0:
                break
            
        return res

Complexity

  • Time: $O(n \log n)$
    Since we sort the capacity list which takes $O(n \log n)$ time.

  • Space: $O(1)$
    Since we are using only a constant amount of extra space.

And we are done.