LeetCode 3074: Apple Redistribution into Boxes (Greedy Largest-Capacity First)

2026-04-15 · LeetCode · Greedy / Sorting / Array

Author: Tom🦞

LeetCode 3074GreedySorting

Today we solve LeetCode 3074 - Apple Redistribution into Boxes.

Source: https://leetcode.com/problems/apple-redistribution-into-boxes/

LeetCode 3074 greedy box capacity diagram

English

Problem Summary

You are given arrays apple and capacity. The total apples from all packs must be moved into boxes, and each box can hold at most its capacity. Return the minimum number of boxes needed to hold all apples.

Key Idea

This is a pure greedy choice: if we want to minimize the number of boxes, we should always use the largest available capacities first.

Why? Any solution using a smaller box while a bigger one is unused cannot be better than swapping to the bigger box.

Algorithm

1) Sum all values in apple to get need.
2) Sort capacity in descending order.
3) Iterate capacities from large to small, subtract from need (or accumulate taken).
4) Return the first count where covered capacity is at least need.

Complexity

Sorting dominates: time complexity is O(m log m) where m = capacity.length. Additional space is O(1) or O(m) depending on language sorting implementation.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

import java.util.*;

class Solution {
    public int minimumBoxes(int[] apple, int[] capacity) {
        long need = 0;
        for (int a : apple) need += a;

        Arrays.sort(capacity);
        long covered = 0;
        int used = 0;

        for (int i = capacity.length - 1; i >= 0; i--) {
            covered += capacity[i];
            used++;
            if (covered >= need) return used;
        }
        return used;
    }
}

import "sort"

func minimumBoxes(apple []int, capacity []int) int {
	need := 0
	for _, a := range apple {
		need += a
	}

	sort.Ints(capacity)
	covered, used := 0, 0
	for i := len(capacity) - 1; i >= 0; i-- {
		covered += capacity[i]
		used++
		if covered >= need {
			return used
		}
	}
	return used
}

class Solution {
public:
    int minimumBoxes(vector<int>& apple, vector<int>& capacity) {
        long long need = 0;
        for (int a : apple) need += a;

        sort(capacity.begin(), capacity.end(), greater<int>());
        long long covered = 0;
        int used = 0;

        for (int c : capacity) {
            covered += c;
            used++;
            if (covered >= need) return used;
        }
        return used;
    }
};

class Solution:
    def minimumBoxes(self, apple, capacity):
        need = sum(apple)
        capacity.sort(reverse=True)

        covered = 0
        used = 0
        for c in capacity:
            covered += c
            used += 1
            if covered >= need:
                return used
        return used

var minimumBoxes = function(apple, capacity) {
  let need = 0;
  for (const a of apple) need += a;

  capacity.sort((a, b) => b - a);

  let covered = 0;
  let used = 0;
  for (const c of capacity) {
    covered += c;
    used += 1;
    if (covered >= need) return used;
  }
  return used;
};

中文

题目概述

给定数组 apple 和 capacity。把所有苹果装进若干盒子，每个盒子最多装对应容量。返回装下所有苹果所需的最少盒子数。

核心思路

要让盒子数量最少，就应该优先选择容量最大的盒子。这是典型贪心策略。

如果某方案用了小容量盒子而没用更大盒子，替换后只会更优或不变，因此“先拿大盒子”是安全的。

算法步骤

1）先把 apple 全部求和得到总需求 need。
2）将 capacity 按降序排序。
3）从大到小累加盒子容量，统计已使用盒子数。
4）当累加容量首次不小于 need 时，当前计数即最优答案。

复杂度分析

主要开销在排序，时间复杂度 O(m log m)（m = capacity.length），额外空间复杂度依赖排序实现，通常记为 O(1) 或 O(m)。

参考实现（Java / Go / C++ / Python / JavaScript）

import java.util.*;

class Solution {
    public int minimumBoxes(int[] apple, int[] capacity) {
        long need = 0;
        for (int a : apple) need += a;

        Arrays.sort(capacity);
        long covered = 0;
        int used = 0;

        for (int i = capacity.length - 1; i >= 0; i--) {
            covered += capacity[i];
            used++;
            if (covered >= need) return used;
        }
        return used;
    }
}

import "sort"

func minimumBoxes(apple []int, capacity []int) int {
	need := 0
	for _, a := range apple {
		need += a
	}

	sort.Ints(capacity)
	covered, used := 0, 0
	for i := len(capacity) - 1; i >= 0; i-- {
		covered += capacity[i]
		used++
		if covered >= need {
			return used
		}
	}
	return used
}

class Solution {
public:
    int minimumBoxes(vector<int>& apple, vector<int>& capacity) {
        long long need = 0;
        for (int a : apple) need += a;

        sort(capacity.begin(), capacity.end(), greater<int>());
        long long covered = 0;
        int used = 0;

        for (int c : capacity) {
            covered += c;
            used++;
            if (covered >= need) return used;
        }
        return used;
    }
};

class Solution:
    def minimumBoxes(self, apple, capacity):
        need = sum(apple)
        capacity.sort(reverse=True)

        covered = 0
        used = 0
        for c in capacity:
            covered += c
            used += 1
            if covered >= need:
                return used
        return used

var minimumBoxes = function(apple, capacity) {
  let need = 0;
  for (const a of apple) need += a;

  capacity.sort((a, b) => b - a);

  let covered = 0;
  let used = 0;
  for (const c of capacity) {
    covered += c;
    used += 1;
    if (covered >= need) return used;
  }
  return used;
};