Apple Redistribution into Boxes — Easy Problem & Solution

Problem statement

apple[i] apples are packed in the i-th pack, and capacity[j] is how many apples box j holds. A pack's apples may be split across boxes.

Return the minimum number of boxes needed to hold every apple. The input always allows a solution.

Example 1

Input: apple = [1,3,2], capacity = [4,3,1,5,2]
Output: 2
Explanation: Six apples fit in the boxes of size 5 and 4.

Example 2

Input: apple = [5,5,5], capacity = [2,4,2,7]
Output: 4
Explanation: Fifteen apples need every box.

Example 3

Input: apple = [1], capacity = [10]
Output: 1

Constraints

• 1 <= apple.length <= 50
• 1 <= capacity.length <= 50
• 1 <= apple[i], capacity[i] <= 50
• The input is generated so that it is possible to redistribute the apples.

How to solve Apple Redistribution into Boxes

Splitting packs means only the total count matters, so sort the capacities largest-first and take boxes until their combined capacity reaches the total.

Approach

1. Sum the apples.
2. Sort capacity descending.
3. Take boxes in that order, subtracting each capacity, until the remaining total is non-positive.
4. Return how many boxes were taken.

Why it works

Splitting is what collapses this to a single number: without it, packs would have to be assigned whole and the problem would become bin packing. With it, any set of boxes whose capacities sum to at least the total works, so the greedy largest-first choice is optimal.

Complexity

• Time — O(m log m)
• Space — O(m)

Pitfalls

• Sorting ascending uses more boxes than necessary.
• The individual pack sizes never matter, only the total.
• The loop must stop as soon as the total is covered.

Reference solution

Python

from typing import List

def minimumBoxes(apple: List[int], capacity: List[int]) -> int:
    total = sum(apple)
    used = 0
    for c in sorted(capacity, reverse=True):
        if total <= 0:
            break
        total -= c
        used += 1
    return used

JavaScript

var minimumBoxes = function(apple, capacity) {
    var total = 0, i;
    for (i = 0; i < apple.length; i++) total += apple[i];
    var sorted = capacity.slice();
    sorted.sort(function(a, b) { return b - a; });
    var used = 0;
    for (i = 0; i < sorted.length; i++) {
        if (total <= 0) break;
        total -= sorted[i];
        used++;
    }
    return used;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Special Array I Easy
• Type of Triangle Easy
• Find the Losers of the Circular Game Easy
• Form Smallest Number From Two Digit Arrays Easy
• Delete Greatest Value in Each Row Easy
• The Employee That Worked on the Longest Task Easy