Leetcode 1710. Maximum Units on a Truck

Problem Explanation:

You are given a 2D array boxTypes where each element represents the number of boxes of a specific type and the number of units within each box of that type. You are also given the maximum number of boxes that can be placed into a truck, denoted as truckSize.

Your task is to determine the maximum number of units that can be placed on the truck by selecting the box types in any order, without exceeding the truck size limit.

For example, consider the following input:

boxTypes = [[1, 3], [2, 2], [3, 1]] truckSize = 4

This means there is 1 box of type 1 with 3 units, 2 boxes of type 2 with 2 units each, and 3 boxes of the type 3 with 1 unit each. You can fit a maximum of 4 boxes on the truck.

One possible way to achieve the maximum number of units on the truck is to take all boxes of the first and second types, and one box of the third type. Therefore, the total number of units would be (1 * 3) + (2 * 2) + (1 * 1) = 8.

Solution Approach:

The best approach to solve this problem is to use a greedy algorithm. Since the goal is to maximize the number of units on the truck, we should prioritize boxes with higher unit counts. First, we will sort the boxTypes array in descending order according to the number of units per box. Then we will iterate through the sorted array, adding as many boxes as possible without exceeding the truckSize limit.

Here is a step-by-step approach to solving the example input:

1. Sort the boxTypes array in descending order of units: [[1, 3], [2, 2], [3, 1]]
2. Initialize the totalUnits and currentBoxes variables to 0
3. Iterate through the sorted array: a. Add the current box type's boxes to currentBoxes and the product of the current box type's boxes and units to totalUnits b. Subtract the current box type's boxes from truckSize c. Check if the truckSize becomes 0, if so, break out of the loop and return totalUnits

Now let's implement the solution in various programming languages:

Python

1class Solution:
2    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:
3        boxTypes.sort(key=lambda x: x[1], reverse=True)
4        total_units = 0
5
6        for numberOfBoxes, numberOfUnits in boxTypes:
7            if truckSize == 0:
8                break
9
10            current_boxes = min(truckSize, numberOfBoxes)
11            total_units += current_boxes * numberOfUnits
12            truckSize -= current_boxes
13
14        return total_units

Java

1import java.util.Arrays;
2import java.util.Comparator;
3
4class Solution {
5    public int maximumUnits(int[][] boxTypes, int truckSize) {
6        Arrays.sort(boxTypes, Comparator.comparingInt(a -> -a[1]));
7        int totalUnits = 0;
8
9        for (int[] boxType : boxTypes) {
10            if (truckSize == 0) {
11                break;
12            }
13
14            int currentBoxes = Math.min(truckSize, boxType[0]);
15            totalUnits += currentBoxes * boxType[1];
16            truckSize -= currentBoxes;
17        }
18
19        return totalUnits;
20    }
21}

JavaScript

1/**
2 * @param {number[][]} boxTypes
3 * @param {number} truckSize
4 * @return {number}
5 */
6var maximumUnits = function(boxTypes, truckSize) {
7    boxTypes.sort((a, b) => b[1] - a[1]);
8    let totalUnits = 0;
9
10    for (const [numberOfBoxes, numberOfUnits] of boxTypes) {
11        if (truckSize === 0) {
12            break;
13        }
14
15        const currentBoxes = Math.min(truckSize, numberOfBoxes);
16        totalUnits += currentBoxes * numberOfUnits;
17        truckSize -= currentBoxes;
18    }
19
20    return totalUnits;
21};

C++

1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    int maximumUnits(std::vector<std::vector<int>>& boxTypes, int truckSize) {
7        std::sort(boxTypes.begin(), boxTypes.end(), [](const std::vector<int>& a, const std::vector<int>& b) {
8            return a[1] > b[1];
9        });
10        int totalUnits = 0;
11
12        for (const auto& boxType : boxTypes) {
13            if (truckSize == 0) {
14                break;
15            }
16
17            int currentBoxes = std::min(truckSize, boxType[0]);
18            totalUnits += currentBoxes * boxType[1];
19            truckSize -= currentBoxes;
20        }
21
22        return totalUnits;
23    }
24};

C#

1using System.Linq;
2
3public class Solution {
4    public int MaximumUnits(int[][] boxTypes, int truckSize) {
5        boxTypes = boxTypes.OrderByDescending(x => x[1]).ToArray();
6        int totalUnits = 0;
7
8        foreach (var boxType in boxTypes) {
9            if (truckSize == 0) {
10                break;
11            }
12
13            int currentBoxes = Math.Min(truckSize, boxType[0]);
14            totalUnits += currentBoxes * boxType[1];
15            truckSize -= currentBoxes;
16        }
17
18        return totalUnits;
19    }
20}
21```### Ruby
22
23```ruby
24class Solution
25    def maximum_units(box_types, truck_size)
26        box_types = box_types.sort_by { |a| -a[1] }
27        total_units = 0
28
29        box_types.each do |number_of_boxes, number_of_units|
30            break if truck_size == 0
31
32            current_boxes = [truck_size, number_of_boxes].min
33            total_units += current_boxes * number_of_units
34            truck_size -= current_boxes
35        end
36
37        total_units
38    end
39end

Go

1import (
2	"sort"
3)
4
5func maximumUnits(boxTypes [][]int, truckSize int) int {
6	sort.Slice(boxTypes, func(i, j int) bool {
7		return boxTypes[i][1] > boxTypes[j][1]
8	})
9	totalUnits := 0
10
11	for _, boxType := range boxTypes {
12		if truckSize == 0 {
13			break
14		}
15
16		currentBoxes := Min(truckSize, boxType[0])
17		totalUnits += currentBoxes * boxType[1]
18		truckSize -= currentBoxes
19	}
20
21	return totalUnits
22}
23
24func Min(a, b int) int {
25	if a < b {
26		return a
27	}
28	return b
29}

These implementations use a greedy approach to maximize the total number of units that can be placed on the truck. By sorting the box types in descending order of units and continuously choosing the highest unit count that can fit, we can ensure the maximum number of units are placed in the truck within the size constraint.