Start learning free

LESSON 333 OF 347 · GREEDY

Maximum Units on a Truck in C#: Greedy Sort by Units per Box

Practice Greedy, O(n log n) Read the full explanation

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 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 the maximum total number of units that can be put on the truck.

Example 1

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

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 <= 106
STEP 1 OF 7
    Ctrl + Enter to check

    C# · GREEDY

    Maximum Units On A Truck in C#, explained

    Problem overview

    boxTypes is an array of pairs. In each pair, box[0] is how many boxes of that type exist and box[1] is how many units each of those boxes holds. The truck takes at most truckSize boxes in total, and MaximumUnits returns the most units you can load.

    For boxTypes = [[1,3],[2,2],[3,1]] and truckSize = 4, you take the one box worth 3 units, the two boxes worth 2 units each, and one of the 1-unit boxes. That gives 3 + 4 + 1 = 8. For [[5,10],[2,5],[4,7],[3,9]] with truckSize = 10, the answer is 91.

    Approach: densest boxes first

    Every box uses exactly one slot on the truck, whatever its size. The only thing that distinguishes boxes is the number of units inside. So at every moment the best choice is the box with the most units that is still available. This is a greedy argument: if a truck held a less valuable box while a more valuable one stayed behind, swapping them would never lose units.

    This is not the knapsack problem, even though it looks similar. In a knapsack, items have different weights, so a valuable heavy item can crowd out two lighter ones. Here every box weighs the same single slot, so value alone decides the order, and no table of subproblems is needed.

    The plan:

    1. Sort the box types by units per box, largest first.
    2. Walk through the sorted types and take as many boxes of each as still fit.
    3. Stop when the truck is full.

    On the second example the sorted types are [5,10], [3,9], [4,7], [2,5]. You take 5 boxes of 10 units (50), then 3 of 9 (27), which leaves 2 slots. Two of the 7-unit boxes add 14, and the truck is full. The total is 91.

    As a trace, with the sorted order above and truckSize = 10:

    Box typetakeunits addedunits so fartruckSize left
    [5,10]550505
    [3,9]327772
    [4,7]214910

    After the third row the truck is full, so the remaining type [2,5] is never visited.

    Step by step

    1. Sort boxTypes in place with Array.Sort and a comparison lambda that orders by the second element, largest first.
    2. Declare units at 0 as the running total.
    3. Loop over the sorted types with foreach. Each element is an int[] named box.
    4. Compute take as the smaller of box[0] (how many exist) and truckSize (how many fit).
    5. Add take * box[1] to units.
    6. Subtract take from truckSize. When it reaches 0, leave the loop. The loop would end correctly without the break, because take would be 0 from then on, but stopping early avoids useless work.
    7. Return units.

    The solution in C#

    class Solution {
    public int MaximumUnits(int[][] boxTypes, int truckSize) {
        Array.Sort(boxTypes, (a, b) => b[1] - a[1]);
        int units = 0;
        foreach (int[] box in boxTypes) {
            int take = Math.Min(box[0], truckSize);
            units += take * box[1];
            truckSize -= take;
            if (truckSize == 0) {
                break;
            }
        }
        return units;
    }
}

    The C# details:

    • The array type. int[][] is a jagged array: an array whose elements are themselves int[] arrays. It is different from the rectangular int[,]. Each inner array here has two elements.
    • Sorting with a lambda. Array.Sort(array, comparison) takes a Comparison<T>. A negative result means a goes first, so b[1] - a[1] puts larger unit counts earlier. With the constraints in this lesson (values up to 1000) the subtraction can't overflow.
    • It sorts in place. The caller's boxTypes array ends up reordered. The method reorders the very array it was given, not a copy.
    • Parameters are local. truckSize -= take changes only the method's own copy of the number.
    • Math.Min is in the System namespace and takes two numbers.

    Why the loop never overfills the truck

    take is capped by truckSize, so truckSize can reach 0 but never goes negative. After that, every later type would get take = 0. That is also why the early break is a pure optimisation. It doesn't change the answer, and it matters little because the sort already dominates the running time.

    Complexity

    Time: O(n log n) for n box types, dominated by the sort. The loop afterwards is O(n). Space: a few integers, plus whatever the sort uses internally. The array is sorted in place, so no copy is made.

    The total in units stays below about a billion under the constraints (at most 1,000,000 boxes of at most 1000 units), which fits in an int.

    Edge cases and common mistakes

    • Sorting by the wrong field. Ordering by box[0], the number of boxes, ignores what is inside them.
    • Ascending order. a[1] - b[1] loads the poorest boxes first and gives a smaller total.
    • Taking whole types only. The last type may need a partial load. In the first example you take just one of the three 1-unit boxes, so the amount is Math.Min(box[0], truckSize), not box[0].
    • A truck bigger than the supply. If truckSize exceeds the total number of boxes, you simply take everything. [[1,3]] with truckSize = 10 gives 3.

    Testing

    • [[1,3],[2,2],[3,1]], truckSize = 4 gives 8.
    • [[5,10],[2,5],[4,7],[3,9]], truckSize = 10 gives 91.
    • [[1,3]], truckSize = 10 gives 3.
    • [[1000,1000],[1000,1000]], truckSize = 2000 gives 2000000.
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free