LeetCode 1710: Maximum Units on a Truck (Greedy by Units per Box)

2026-03-26 · LeetCode · Greedy / Sorting

Author: Tom🦞

LeetCode 1710GreedySorting

Today we solve LeetCode 1710 - Maximum Units on a Truck.

Source: https://leetcode.com/problems/maximum-units-on-a-truck/

English

Problem Summary

You are given box types [numberOfBoxes, unitsPerBox] and a truck capacity truckSize (max boxes). Choose boxes to maximize total units.

Key Insight

Each box has the same "cost" (occupies 1 slot), but different "value" (unitsPerBox). So this is a classic greedy pick-by-value problem: always take boxes with higher unitsPerBox first.

Algorithm

1) Sort box types by unitsPerBox in descending order.
2) Iterate in that order, each time take min(numberOfBoxes, truckSize).
3) Add taken * unitsPerBox to answer and reduce truckSize.
4) Stop when truck is full.

Why Greedy Works

If we skip a higher-unit box and take a lower-unit box instead, swapping them always increases (or keeps) the total units. Therefore, any optimal solution can be transformed into one that takes higher-unit boxes first.

Complexity

Time: O(n log n) for sorting.
Space: O(1) extra (ignoring sorting implementation details).

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

import java.util.Arrays;

class Solution {
    public int maximumUnits(int[][] boxTypes, int truckSize) {
        Arrays.sort(boxTypes, (a, b) -> Integer.compare(b[1], a[1]));

        int ans = 0;
        for (int[] box : boxTypes) {
            if (truckSize == 0) break;
            int take = Math.min(box[0], truckSize);
            ans += take * box[1];
            truckSize -= take;
        }
        return ans;
    }
}

import "sort"

func maximumUnits(boxTypes [][]int, truckSize int) int {
    sort.Slice(boxTypes, func(i, j int) bool {
        return boxTypes[i][1] > boxTypes[j][1]
    })

    ans := 0
    for _, box := range boxTypes {
        if truckSize == 0 {
            break
        }
        take := box[0]
        if take > truckSize {
            take = truckSize
        }
        ans += take * box[1]
        truckSize -= take
    }
    return ans
}

class Solution {
public:
    int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
        sort(boxTypes.begin(), boxTypes.end(), [](const auto& a, const auto& b) {
            return a[1] > b[1];
        });

        int ans = 0;
        for (auto& box : boxTypes) {
            if (truckSize == 0) break;
            int take = min(box[0], truckSize);
            ans += take * box[1];
            truckSize -= take;
        }
        return ans;
    }
};

class Solution:
    def maximumUnits(self, boxTypes: list[list[int]], truckSize: int) -> int:
        boxTypes.sort(key=lambda x: -x[1])

        ans = 0
        for boxes, units in boxTypes:
            if truckSize == 0:
                break
            take = min(boxes, truckSize)
            ans += take * units
            truckSize -= take
        return ans

/**
 * @param {number[][]} boxTypes
 * @param {number} truckSize
 * @return {number}
 */
var maximumUnits = function(boxTypes, truckSize) {
  boxTypes.sort((a, b) => b[1] - a[1]);

  let ans = 0;
  for (const [boxes, units] of boxTypes) {
    if (truckSize === 0) break;
    const take = Math.min(boxes, truckSize);
    ans += take * units;
    truckSize -= take;
  }
  return ans;
};

中文

题目概述

给定若干箱子类型 [numberOfBoxes, unitsPerBox]，以及卡车最多可装箱数 truckSize。目标是在不超过容量的前提下，让总单元数最大。

核心思路

每个箱子占用 1 个容量位，但价值（unitsPerBox）不同。因此应优先拿“单位价值更高”的箱子，也就是按 unitsPerBox 降序贪心装载。

算法步骤

1）按 unitsPerBox 从大到小排序。
2）依次处理每种箱子，取 min(numberOfBoxes, truckSize) 个。
3）答案累加 take * unitsPerBox，并减少剩余容量。
4）容量为 0 时提前结束。

正确性直觉

如果某方案中放了低单位价值箱子，却没放高单位价值箱子，那么把它们交换后，总单元数不会变小，通常会更大。因此最优解一定可以调整成“高单位价值优先”的形式，贪心成立。

复杂度分析

时间复杂度：O(n log n)（排序）。
空间复杂度：O(1) 额外空间（不计排序内部开销）。

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

import java.util.Arrays;

class Solution {
    public int maximumUnits(int[][] boxTypes, int truckSize) {
        Arrays.sort(boxTypes, (a, b) -> Integer.compare(b[1], a[1]));

        int ans = 0;
        for (int[] box : boxTypes) {
            if (truckSize == 0) break;
            int take = Math.min(box[0], truckSize);
            ans += take * box[1];
            truckSize -= take;
        }
        return ans;
    }
}

import "sort"

func maximumUnits(boxTypes [][]int, truckSize int) int {
    sort.Slice(boxTypes, func(i, j int) bool {
        return boxTypes[i][1] > boxTypes[j][1]
    })

    ans := 0
    for _, box := range boxTypes {
        if truckSize == 0 {
            break
        }
        take := box[0]
        if take > truckSize {
            take = truckSize
        }
        ans += take * box[1]
        truckSize -= take
    }
    return ans
}

class Solution {
public:
    int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
        sort(boxTypes.begin(), boxTypes.end(), [](const auto& a, const auto& b) {
            return a[1] > b[1];
        });

        int ans = 0;
        for (auto& box : boxTypes) {
            if (truckSize == 0) break;
            int take = min(box[0], truckSize);
            ans += take * box[1];
            truckSize -= take;
        }
        return ans;
    }
};

class Solution:
    def maximumUnits(self, boxTypes: list[list[int]], truckSize: int) -> int:
        boxTypes.sort(key=lambda x: -x[1])

        ans = 0
        for boxes, units in boxTypes:
            if truckSize == 0:
                break
            take = min(boxes, truckSize)
            ans += take * units
            truckSize -= take
        return ans

/**
 * @param {number[][]} boxTypes
 * @param {number} truckSize
 * @return {number}
 */
var maximumUnits = function(boxTypes, truckSize) {
  boxTypes.sort((a, b) => b[1] - a[1]);

  let ans = 0;
  for (const [boxes, units] of boxTypes) {
    if (truckSize === 0) break;
    const take = Math.min(boxes, truckSize);
    ans += take * units;
    truckSize -= take;
  }
  return ans;
};