LC 1710. 卡车上的最大单元数

题目描述

这是 LeetCode 上的 1710. 卡车上的最大单元数 ，难度为 简单。

请你将一些箱子装在 一辆卡车 上。给你一个二维数组 boxTypes，其中 $boxTypes[i] = [numberOfBoxes_i, numberOfUnitsPerBox_i]$ ：

  • $numberOfBoxes_i$ 是类型 i 的箱子的数量。
  • $numberOfUnitsPerBox_i$ 是类型 i 每个箱子可以装载的单元数量。

整数 truckSize 表示卡车上可以装载 箱子 的 最大数量 。只要箱子数量不超过 truckSize，你就可以选择任意箱子装到卡车上。

返回卡车可以装载 单元 的 最大 总数。

示例 1：

1
2
3
4
5
6
7
8
9
10
输入：boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4

输出：8

解释：箱子的情况如下：
- 1 个第一类的箱子，里面含 3 个单元。
- 2 个第二类的箱子，每个里面含 2 个单元。
- 3 个第三类的箱子，每个里面含 1 个单元。
可以选择第一类和第二类的所有箱子，以及第三类的一个箱子。
单元总数 = (1 * 3) + (2 * 2) + (1 * 1) = 8

示例 2：
1
2
3
输入：boxTypes = [[5,10],[2,5],[4,7],[3,9]], truckSize = 10

输出：91

提示：

  • $1 <= boxTypes.length <= 1000$
  • $1 <= numberOfBoxes_i, numberOfUnitsPerBox_i <= 1000$
  • $1 <= truckSize <= 10^6$

贪心

为了方便，我们令 boxTypes 为 bs，令 truckSize 为 k。

由于每个箱子成本相同（均占用一个箱子位置），因此在 k 给定的情况下，我们应当尽可能选择装载单元数量大的箱子。

这引导我们可以将 bs 根据「装载单元数量」排倒序，然后从前往后 pick 箱子，直到没有空闲位置。

Java 代码：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int maximumUnits(int[][] bs, int k) {
        int n = bs.length, ans = 0;
        Arrays.sort(bs, (a,b)->b[1]-a[1]);
        for (int i = 0, cnt = 0; i < n && cnt < k; i++) {
            int a = bs[i][0], b = bs[i][1], c = Math.min(a, k - cnt);
            cnt += c; ans += c * b;
        }
        return ans;
    }
}

TypeScript 代码：
1
2
3
4
5
6
7
8
9
function maximumUnits(bs: number[][], k: number): number {
    let n = bs.length, ans = 0
    bs.sort((a,b)=>b[1]-a[1])
    for (let i = 0, cnt = 0; i < n && cnt < k; i++) {
        const a = bs[i][0], b = bs[i][1], c = Math.min(a, k - cnt)
        cnt += c; ans += c * b
    }
    return ans
}

Python 代码：
1
2
3
4
5
6
7
8
9
10
class Solution:
    def maximumUnits(self, bs: List[List[int]], k: int) -> int:
        bs.sort(key=lambda x: -x[1])
        n, ans = len(bs), 0
        idx, cnt = 0, 0
        while idx < n and cnt < k:
            a, b, c = bs[idx][0], bs[idx][1], min(bs[idx][0], k - cnt)
            cnt, ans = cnt + c, ans + b * c
            idx += 1
        return ans

  • 时间复杂度：排序复杂度为 $O(n\log{n})$，同时答案复杂度为 $O(n)$。整体复杂度为 $O(n\log{n})$
  • 空间复杂度：$O(\log{n})$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1710 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。