Apple Redistribution into Boxes

Difficulty: Easy | Acceptance: 78.50% | Paid: No Topics: Array, Greedy, Sorting

You are given an array apple of size n and an array capacity of size m.

The array apple denotes the weight of the i-th apple, and the array capacity denotes the maximum capacity of the j-th box.

You have to redistribute the apples into the boxes such that each box can hold at most one apple (Note: The problem statement implies we are summing weights to fit into boxes, effectively treating apples as divisible weight units for the purpose of capacity calculation in the standard solution, or fitting whole apples if constraints allow. The standard “Easy” solution treats this as a volume fitting problem).

Return the minimum number of boxes required to redistribute all the apples.

• Examples
• Constraints
• Brute Force (Backtracking)
• Greedy (Sorting Capacities)

Examples

Input: apple = [1,3,2], capacity = [4,3,1,5,2]
Output: 2
Explanation: 
We can use the box with capacity 5 and the box with capacity 3.
Total weight of apples = 1 + 3 + 2 = 6.
5 + 3 = 8 >= 6. So 2 boxes are enough.

Input: apple = [5,5,5], capacity = [2,4,2,7]
Output: 4
Explanation:
Total weight of apples = 15.
We need to use all boxes: 2 + 4 + 2 + 7 = 15.

Constraints

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 all apples.

Brute Force (Backtracking)

Intuition We can try every possible combination of boxes to find the smallest subset whose total capacity is greater than or equal to the total weight of the apples. This checks all subsets of the capacity array.

Steps

• Calculate the total weight of all apples.
• Use recursion/backtracking to explore including or excluding each box in the current subset.
• Keep track of the minimum number of boxes used that satisfies the total weight requirement.

class Solution:
    def minBoxes(self, apple: list[int], capacity: list[int]) -> int:
        target = sum(apple)
        n = len(capacity)
        self.ans = n  # Worst case: use all boxes
        
        def backtrack(idx, current_sum, count):
            if current_sum >= target:
                self.ans = min(self.ans, count)
                return
            if idx == n:
                return
            # Pruning: if we already used more boxes than best found, stop
            if count >= self.ans:
                return
            
            # Include current box
            backtrack(idx + 1, current_sum + capacity[idx], count + 1)
            # Exclude current box
            backtrack(idx + 1, current_sum, count)
            
        backtrack(0, 0, 0)
        return self.ans

Complexity

• Time: O(2ᵐ) where m is the number of boxes. We explore all subsets.
• Space: O(m) for the recursion stack.
• Notes: This approach is conceptually simple but will Time Limit Exceed (TLE) for larger inputs. It serves as a baseline for understanding the problem.

Greedy (Sorting Capacities)

Intuition To minimize the number of boxes, we should prioritize using boxes with the largest capacities first. By sorting the boxes in descending order and accumulating their capacities until the total meets or exceeds the total weight of the apples, we guarantee the minimum number of boxes.

Steps

• Calculate the total weight of the apples.
• Sort the capacity array in descending order.
• Iterate through the sorted capacities, adding each box’s capacity to a running sum.
• Increment a counter for each box used. Stop when the running sum is greater than or equal to the total apple weight.

class Solution:
    def minBoxes(self, apple: list[int], capacity: list[int]) -> int:
        total_apples = sum(apple)
        capacity.sort(reverse=True)
        
        current_capacity = 0
        boxes_used = 0
        
        for cap in capacity:
            current_capacity += cap
            boxes_used += 1
            if current_capacity >= total_apples:
                return boxes_used
                
        return -1 # Should not reach here given problem constraints

Complexity

• Time: O(n log n + m log m) due to sorting, where n is the number of apples and m is the number of boxes.
• Space: O(1) or O(m) depending on the sorting implementation (in-place sort usually uses O(log m) stack space).
• Notes: This is the optimal approach for this problem, efficiently minimizing the number of boxes by leveraging the greedy strategy.