Maximum Units on a Truck

class Solution {
public:
    int maxUnits(vector<vector<int>>& boxTypes, int truckSize) {
        priority_queue<vector<int>, vector<vector<int>>, CompareUnits> pq;
        for (auto type : boxTypes) {
            pq.push(type);
        }
        int totalCount = 0;
        while (!pq.empty()) {
            vector<int> current = pq.top();
            pq.pop();
            int count = min(truckSize, current[0]);
            totalCount += count * current[1];
            truckSize -= count;
            if(truckSize == 0)
                break;
        }
        return totalCount;
    }

    struct CompareUnits {
        bool operator()(vector<int> const& a, vector<int> const& b) {
            return a[1] < b[1];
        }
    };
};

The provided C++ code solves the problem of determining the maximum number of units that can be placed on a truck given constraints on the truck size and the number of boxes available. Here's a breakdown of how the code addresses this:

• The function maxUnits receives two inputs: a vector<vector<int>>& representing different box types where each box type vector consists of two integers (the number of boxes and units per box), and an int representing the maximum capacity of the truck in terms of the number of boxes it can carry.
• A priority queue pq is used with a custom comparator CompareUnits. This comparator ensures that the box types with the higher number of units per box are prioritized.
• The code iterates through the provided box types and pushes each into the priority queue.
• An integer totalCount is initialized to accumulate the total units loaded onto the truck.
• Within a loop, the top element (which has the maximum units per box due to the priority queue's ordering) is fetched and removed from the priority queue.
• For the current box type, the smaller number between the truck's remaining capacity (truckSize) and the number of available boxes (current[0]) is determined.
• The total count of units is increased by multiplying the chosen number of boxes by their respective units per box and this number is subtracted from the truck's total available capacity.
• If the truck is fully loaded (truckSize becomes 0), the loop breaks.
• The function returns the total units that can be carried on the truck.

This efficient approach ensures that priority is given to loading boxes with the highest units per box first, thereby maximizing the total units on the truck until its capacity is reached.

class Solution {
public:
    int maxUnits(int[][] types, int capacity) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) -> y[1] - x[1]);
        pq.addAll(Arrays.asList(types));
        int totalUnits = 0;
        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int count = Math.min(capacity, current[0]);
            totalUnits += count * current[1];
            capacity -= count;
            if(capacity == 0)
                break;
        }
        return totalUnits;
    }
}

The Java solution provided for the "Maximum Units on a Truck" problem efficiently calculates the maximum units that can be loaded into a truck given a set of box types and a truck's capacity. The approach uses a priority queue to sort the box types by the number of units each box can hold in descending order, ensuring that the boxes with the most units are considered first.

• Initialize a PriorityQueue in descending order of units per box type. This optimizes the selection process by always polling the box type with the highest units first.
• Convert the array of box types into a list and add all elements to the priority queue.
• Keep track of the total units loaded and the remaining capacity of the truck.
• Extract the box type from the front of the priority queue and load as many of those boxes as possible without exceeding the truck's capacity.
• Decrease the remaining truck capacity by the number of boxes just loaded.
• If the truck is fully loaded (capacity reaches zero), exit the loop as no more boxes can be added.

The algorithm ensures that the truck is loaded with the maximum possible units by prioritizing boxes with higher units and efficiently managing the available truck capacity, stopping early if the truck is full. This method provides a balanced approach combining efficiency with simplicity.