#3074

Easy

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Apple Redistribution into Boxes

Name: Interview AiBox
Availability: InStock
Rating: 4.9 (10000 reviews)

Distribute packs of apples into boxes using a greedy strategy, minimizing the number of boxes selected efficiently and correctly.

array greedy sorting

Problem Statement

You are given an array apple where apple[i] represents the number of apples in the ith pack, and an array capacity representing the capacity of each available box. Your task is to select boxes to redistribute all apple packs so that no box exceeds its capacity.

Return the minimum number of boxes required to redistribute all apple packs. It is guaranteed that the input is valid, so a redistribution is always possible. For example, with apple = [1,3,2] and capacity = [4,3,1,5,2], the minimum number of boxes needed is 2.

Examples

Example 1

Input: apple = [1,3,2], capacity = [4,3,1,5,2]

Output: 2

We will use boxes with capacities 4 and 5. It is possible to distribute the apples as the total capacity is greater than or equal to the total number of apples.

Example 2

Input: apple = [5,5,5], capacity = [2,4,2,7]

Output: 4

We will need to use all the boxes.

Constraints

1 <= n == apple.length <= 50
1 <= m == capacity.length <= 50
1 <= apple[i], capacity[i] <= 50
The input is generated such that it's possible to redistribute packs of apples into boxes.

Solution Approach

Sort boxes by capacity

Sort the capacity array in non-decreasing order to prioritize larger boxes for greedy allocation. This helps ensure fewer boxes are used by always fitting the largest remaining pack into the largest available space.

Allocate apples greedily

Iterate from the largest box backward and assign packs of apples. Maintain an invariant that the sum of remaining apple packs can still fit into the remaining boxes. Each greedy choice maximizes utilization without exceeding any box capacity.

Count minimum boxes used

Track how many boxes have been selected during allocation. Stop once all apple packs are assigned. This directly yields the minimum number of boxes needed, ensuring correctness and efficiency.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(m log m + n) due to sorting the capacity array and iterating over n packs. Space complexity is O(1) extra space if in-place sorting is used, otherwise O(m) for sorted copy.

What Interviewers Usually Probe

Checks if candidate sorts the capacity array before allocation.
Looks for correct greedy allocation respecting remaining sum invariant.
Wants explanation for why the fewest boxes are sufficient, not just any allocation.

Common Pitfalls or Variants

Common pitfalls

Failing to sort capacities leads to using more boxes than necessary.
Not maintaining the sum invariant can cause incorrect allocation and overshoot.
Confusing pack count with box capacity can produce wrong minimum count.

Follow-up variants

Allow boxes to hold multiple packs but with a maximum total capacity constraint.
Change problem to find maximum number of apple packs in exactly k boxes.
Introduce weight limits per apple pack in addition to box capacity.

FAQ

How do I start solving Apple Redistribution into Boxes?

Begin by sorting the capacity array in non-decreasing order and planning to allocate largest packs first to largest boxes.

Why is greedy allocation appropriate for this problem?

Because each step chooses the box that maximizes apple fit while keeping remaining apples distributable, satisfying the invariant.

Can I use fewer boxes if I ignore sorting?

No, ignoring sorting can lead to inefficient choices that require more boxes than the true minimum.

What is the time complexity of the optimal solution?

Sorting the boxes takes O(m log m), and iterating through packs is O(n), so total time complexity is O(m log m + n).

How does GhostInterview ensure correctness in this problem?

It guides through greedy allocation while validating that remaining apples can fit, preventing common pitfalls like overshooting box counts.

terminal

Solution

Solution 1: Greedy + Sorting

To minimize the number of boxes needed, we should prioritize using boxes with larger capacities. Therefore, we can sort the boxes in descending order of capacity, and then use the boxes one by one until all the apples are packed. We return the number of boxes used at this point.

1

2

3

4

5

6

7

8

class Solution:
    def minimumBoxes(self, apple: List[int], capacity: List[int]) -> int:
        capacity.sort(reverse=True)
        s = sum(apple)
        for i, c in enumerate(capacity, 1):
            s -= c
            if s <= 0:
                return i

Continue Practicing

#3075 maximize happiness of selected children #3068 find the maximum sum of node values #3107 minimum operations to make median of array equal to k