Maximum Units

Problem

You have to place a number of boxes into the truck. You are given a 2D array where each element represents the number of boxes of type ‘i’ and the number of units in the box of type ‘i’, respectively. You are also given an integer, 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 the truck size. Your task is to find the maximum total number of units that can be put on the truck.

Sample Input

[[1, 3], [2, 2], [3,1]]

Sample Output

8

Explanation

We will take all the boxes of the first and second types and a box of the third type. Total number of units will be = (1 * 3) + (2 * 2) + (1 * 1) = 8.

Approach

Simply put, we must prioritize the more valuable boxes first. To accomplish this, we must sort the box types array in decreasing order by the number of units per box. Then we can iterate through B, adding as many boxes as possible at each step until we reach the truck size (T).

To our answer variable, we should add the number of boxes added multiplied by the units per box, and T should be reduced by the same number of boxes. We should return the answer when the truck is full (T == 0) or when the iteration is complete.

Complexity Analysis

The time complexity is O(NlogN)) with space complexity of O(1)

C++ Programming

#include<bits/stdc++.h>

using namespace std;

// function to find maximum number of boxes
int maximumUnits(vector < vector < int >> & arr, int t) {
  
  // sort the array in decreasing order
  sort(arr.begin(), arr.end(), [](auto & a, auto & b) {
    return b[1] < a[1];
  });
  // variable to store the resultant boxes
  int ans = 0;
  
  // iterate the array
  for (auto & b: arr) {
    int c = min(b[0], t);
    // update the answer
    ans += c * b[1], t -= c;
    if (!t) return ans;
  }
  return ans;
}

int main() {
    // initialize the array
  vector < vector < int >> arr {{1, 3}, {2, 2}, {3,1}};
    int t = 4;
    cout << maximumUnits(arr, t);
}

Output

8

Java Programming

import java.io.*;
import java.util.Arrays;

class Solution {
    
    // function to find maximum number of boxes
    public static int maximumUnits(int[][] arr, int t) {
        
        // sort the array in decreasing order
        Arrays.sort(arr, (a,b) -> b[1] - a[1]);
        
        // variable to store the resultant boxes
        int ans = 0;
        
        // iterate the array
        for (int[] b : arr) {
            int c = Math.min(b[0], t);
            
            // update the answer
            ans += c * b[1];
            t -= c;
            if (t == 0) return ans;
        }
        return ans;
    }
    public static void main (String[] args) {
        
        // initialize the array
        int[][] arr = {{1, 3}, {2, 2}, {3,1}};
        int t = 4;
        System.out.println(maximumUnits(arr, t));
    }
}

Output

8

Python Programming

# function to find maximum number of c
def maximumUnits(arr, t):

    # sort the array in decreasing order
    arr.sort(key=lambda x: x[1], reverse=True)

    # variable to store the resultant c
    ans = 0

    # iterate the array
    for b,n in arr:
        c = min(b, t)
        
        # update the answer
        ans += c * n
        t -= c
        if t == 0: return ans
    return ans

# initialize the array
arr = [[1, 3], [2, 2], [3,1]]
t = 4
print(maximumUnits(arr, t))

Output

8

People are also reading:

• Monotonic Array
• Binary Gap
• Arranging Coins
• Missing Numbers
• Mountain Array
• What is Pseudocode?
• Merge Two Sorted Arrays in-place
• Print all subarrays with 0 sum
• Longest subarray with sum as K
• Rod Cutting Problem