Maximum Units on a Truck

🏠 ⬅️ ➡️

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 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

Note: This problem is from LeetCode.
Compiled
Executed
Correct
program main
    implicit none

    integer, parameter :: n_examples = 2
    integer, parameter :: n_boxes = 4
    integer, parameter :: n_types = 3
    integer, parameter :: max_units = 1000
    integer, parameter :: max_truck_size = 1000

    integer :: i, j, k, l
    integer :: boxTypes(n_types, 2)
    integer :: truckSize
    integer :: total_units

    ! Examples
    boxTypes(:, :) = reshape([1, 3, 2, 2, 3, 1], shape=[n_types, 2])
    truckSize = 4
    call solve(boxTypes, truckSize, total_units)
    write (*, '(A, I0, A, I0, A)') 'Example 1: ', total_units, &
        ' units can be put on the truck.'

    boxTypes(:, :) = reshape([5, 10, 2, 5, 4, 7, 3, 9], shape=[n_types, 2])
    truckSize = 10
    call solve(boxTypes, truckSize, total_units)
    write (*, '(A, I0, A, I0, A)') 'Example 2: ', total_units, &
        ' units can be put on the truck.'

contains

    subroutine solve(boxTypes, truckSize, total_units)
        implicit none
        integer, intent(in) :: boxTypes(:, :)
        integer, intent(in) :: truckSize
        integer, intent(out) :: total_units
        integer :: i, j, k, l
        integer :: current_truck_size
        integer :: current_total_units

        current_truck_size = 0
        current_total_units = 0
        do i = 1, size(boxTypes, 1)
            if (current_truck_size + boxTypes(i, 1) > truckSize) then
                exit
            end if
            current_truck_size = current_truck_size + boxTypes(i, 1)
            current_total_units = current_total_units + &
                boxTypes(i, 1) * boxTypes(i, 2)
        end do
        total_units = current_total_units
    end subroutine solve

end program main
Compiled
Executed
Correct
module MaxUnitsOnTruck
    implicit none
    private
    public :: maxUnitsOnTruck
contains
    function maxUnitsOnTruck(boxTypes, truckSize) result(maxUnits)
        integer, intent(in) :: boxTypes(:,:)
        integer, intent(in) :: truckSize
        integer :: maxUnits
        integer :: i, j, numBoxes, numUnits

        maxUnits = 0
        do i = 1, size(boxTypes, 1)
            numBoxes = boxTypes(i, 1)
            numUnits = boxTypes(i, 2)
            if (numBoxes <= truckSize) then
                maxUnits = max(maxUnits, numBoxes * numUnits)
            else
                maxUnits = max(maxUnits, truckSize * numUnits)
                exit
            end if
        end do
    end function maxUnitsOnTruck
end module MaxUnitsOnTruck

program test_maxUnitsOnTruck
    use MaxUnitsOnTruck
    implicit none
    integer, parameter :: truckSize = 4
    integer, parameter :: boxTypes(3, 2) = reshape([1, 3, 2, 2, 3, 1], shape(boxTypes))
    integer :: maxUnits

    maxUnits = maxUnitsOnTruck(boxTypes, truckSize)
    write (*, '(A, I0)') 'Max units on truck: ', maxUnits
end program test_maxUnitsOnTruck
🌐 Data from online sources
import heapq

def busiest_servers(k, arrival, load):
    server_requests = [0] * k
    pq = []
    available_servers = list(range(k))

    for i in range(len(arrival)):
        while pq and pq[0][0] <= arrival[i]:
            _, server_id = heapq.heappop(pq)
            available_servers.append(server_id)

        if available_servers:
            server_id = available_servers.pop(0)
            server_requests[server_id] += 1
            heapq.heappush(pq, (arrival[i] + load[i], server_id))

    max_requests = max(server_requests)
    return [i for i in range(k) if server_requests[i] == max_requests]
1. Initialize an array named `serverRequests` to store the number of requests handled by each server. This array is the same length as the number of servers and filled with 0s initially. Initialize a priority queue `pq` to store the servers that are currently handling a request, in ascending order of when they will finish processing the request. Initialize a queue `availableServers` and fill it with server IDs from 0 to k-1.
  1. Iterate over the arrival array. For each request, dequeue any servers that have finished processing their tasks, and enqueue them into availableServers.
  2. If there are servers available in availableServers, then assign the current request to the first available server. Increment the corresponding count in serverRequests, and enqueue the server into pq with the finish time (arrival[i] + load[i]) as the priority.
  3. Iterate through serverRequests to find the maximum count (i.e. the highest number of requests handled).
  4. Finally, create a result list (or array) containing the IDs of servers with counts equal to the maximum count.
🌐 Data from online sources
#include <vector>
#include <queue>

std::vector<int> busiestServers(int k, std::vector<int>& arrival, std::vector<int>& load) {
    std::vector<int> serverRequests(k, 0);
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;
    std::queue<int> availableServers;

    for (int i = 0; i < k; ++i) {
        availableServers.push(i);
    }

    for (int i = 0; i < arrival.size(); ++i) {
        while (!pq.empty() && pq.top().first <= arrival[i]) {
            availableServers.push(pq.top().second);
            pq.pop();
        }

        if (!availableServers.empty()) {
            int serverId = availableServers.front();
            availableServers.pop();
            serverRequests[serverId]++;
            pq.push({arrival[i] + load[i], serverId});
        }
    }

    int maxRequests = 0;
    for (int requests : serverRequests) {
        maxRequests = std::max(maxRequests, requests);
    }

    std::vector<int> result;
    for (int i = 0; i < k; ++i) {
        if (serverRequests[i] == maxRequests) {
            result.push_back(i);
        }
    }

    return result;
}
1. Initialize an array named `serverRequests` to store the number of requests handled by each server. This array is the same length as the number of servers and filled with 0s initially. Initialize a priority queue `pq` to store the servers that are currently handling a request, in ascending order of when they will finish processing the request. Initialize a queue `availableServers` and fill it with server IDs from 0 to k-1.
  1. Iterate over the arrival array. For each request, dequeue any servers that have finished processing their tasks, and enqueue them into availableServers.
  2. If there are servers available in availableServers, then assign the current request to the first available server. Increment the corresponding count in serverRequests, and enqueue the server into pq with the finish time (arrival[i] + load[i]) as the priority.
  3. Iterate through serverRequests to find the maximum count (i.e. the highest number of requests handled).
  4. Finally, create a result list (or array) containing the IDs of servers with counts equal to the maximum count.