Problem

You are assigned to put some amount of boxes onto one truck. You are given a 2D array boxTypes, where boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi]:

  • numberOfBoxesi is the number of boxes of type i.
  • numberOfUnitsPerBoxi is the number of units in each box of the type i.

You are also given an integer truckSize, which is the maximum number of boxes that can be put on the truck. You can choose any boxes to put on the truck as long as the number of boxes does not exceed truckSize.

Return themaximum total number of units that can be put on the truck.

Examples

Example 1

1
2
3
4
5
6
7
8

Input: boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4
Output: 8
Explanation: There are:
- 1 box of the first type that contains 3 units.
- 2 boxes of the second type that contain 2 units each.
- 3 boxes of the third type that contain 1 unit each.
You can take all the boxes of the first and second types, and one box of the third type.
The total number of units will be = (1 * 3) + (2 * 2) + (1 * 1) = 8.

Example 2

1
2

Input: boxTypes = [[5,10],[2,5],[4,7],[3,9]], truckSize = 10
Output: 91

Constraints

  • 1 <= boxTypes.length <= 1000
  • 1 <= numberOfBoxesi, numberOfUnitsPerBoxi <= 1000
  • 1 <= truckSize <= 10^6

Solution

Method 1 – Greedy Sorting by Units

Intuition

To maximize the total units on the truck, we should prioritize box types with the highest units per box. By sorting box types in descending order of units per box, we can greedily fill the truck with the most valuable boxes first.

Approach

  1. Sort boxTypes by numberOfUnitsPerBox in descending order.
  2. Initialize ans to 0 and iterate through sorted box types:
    • For each type, take as many boxes as possible (up to truckSize).
    • Add the units to ans and decrease truckSize accordingly.
    • Stop if the truck is full.
  3. Return the total units loaded.

Complexity

  • ⏰ Time complexity: O(n log n) — Sorting box types.
  • 🧺 Space complexity: O(1) — In-place sorting and constant extra space.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
        sort(boxTypes.begin(), boxTypes.end(), [](auto& a, auto& b) {
            return a[1] > b[1];
        });
        int ans = 0;
        for (auto& b : boxTypes) {
            int take = min(truckSize, b[0]);
            ans += take * b[1];
            truckSize -= take;
            if (truckSize == 0) break;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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 _, b := range boxTypes {
        take := b[0]
        if truckSize < take { take = truckSize }
        ans += take * b[1]
        truckSize -= take
        if truckSize == 0 { break }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public int maximumUnits(int[][] boxTypes, int truckSize) {
        Arrays.sort(boxTypes, (a, b) -> b[1] - a[1]);
        int ans = 0;
        for (int[] b : boxTypes) {
            int take = Math.min(truckSize, b[0]);
            ans += take * b[1];
            truckSize -= take;
            if (truckSize == 0) break;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    fun maximumUnits(boxTypes: Array<IntArray>, truckSize: Int): Int {
        boxTypes.sortByDescending { it[1] }
        var ans = 0
        var size = truckSize
        for (b in boxTypes) {
            val take = minOf(size, b[0])
            ans += take * b[1]
            size -= take
            if (size == 0) break
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def maximum_units(box_types: list[list[int]], truck_size: int) -> int:
    box_types.sort(key=lambda x: -x[1])
    ans = 0
    for num, units in box_types:
        take = min(truck_size, num)
        ans += take * units
        truck_size -= take
        if truck_size == 0:
            break
    return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

impl Solution {
    pub fn maximum_units(box_types: Vec<Vec<i32>>, truck_size: i32) -> i32 {
        let mut box_types = box_types;
        box_types.sort_by(|a, b| b[1].cmp(&a[1]));
        let mut ans = 0;
        let mut size = truck_size;
        for b in box_types {
            let take = size.min(b[0]);
            ans += take * b[1];
            size -= take;
            if size == 0 { break; }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    maximumUnits(boxTypes: number[][], truckSize: number): number {
        boxTypes.sort((a, b) => b[1] - a[1]);
        let ans = 0;
        for (const [num, units] of boxTypes) {
            const take = Math.min(truckSize, num);
            ans += take * units;
            truckSize -= take;
            if (truckSize === 0) break;
        }
        return ans;
    }
}