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
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
Example 1: 11 units can be put on the truck. Example 2: 25 units can be put on the truck.
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
temp.f95:4:29: 4 | public :: maxUnitsOnTruck | 1 Error: PUBLIC attribute applied to MODULE maxunitsontruck at (1) temp.f95:6:28: 6 | function maxUnitsOnTruck(boxTypes, truckSize) result(maxUnits) | 1 Error: MODULE attribute of ‘maxunitsontruck’ conflicts with PROCEDURE attribute at (1) temp.f95:7:44: 7 | integer, intent(in) :: boxTypes(:,:) | 1 Error: Unexpected data declaration statement in CONTAINS section at (1) temp.f95:8:40: 8 | integer, intent(in) :: truckSize | 1 Error: Unexpected data declaration statement in CONTAINS section at (1) temp.f95:9:27: 9 | integer :: maxUnits | 1 Error: Unexpected data declaration statement in CONTAINS section at (1) temp.f95:10:43: 10 | integer :: i, j, numBoxes, numUnits | 1 Error: Unexpected data declaration statement in CONTAINS section at (1) temp.f95:12:20: 12 | maxUnits = 0 | 1 Error: Unexpected assignment statement in CONTAINS section at (1) temp.f95:13:35: 13 | do i = 1, size(boxTypes, 1) | 1 Error: Unexpected DO statement in CONTAINS section at (1) temp.f95:14:37: 14 | numBoxes = boxTypes(i, 1) | 1 Error: Unexpected assignment statement in CONTAINS section at (1) temp.f95:15:37: 15 | numUnits = boxTypes(i, 2) | 1 Error: Unexpected assignment statement in CONTAINS section at (1) temp.f95:16:43: 16 | if (numBoxes <= truckSize) then | 1 Error: Unexpected block IF statement in CONTAINS section at (1) temp.f95:17:61: 17 | maxUnits = max(maxUnits, numBoxes * numUnits) | 1 Error: Unexpected assignment statement in CONTAINS section at (1) temp.f95:18:16: 18 | else | 1 Error: Unexpected ELSE statement in CONTAINS section at (1) temp.f95:19:62: 19 | maxUnits = max(maxUnits, truckSize * numUnits) | 1 Error: Unexpected assignment statement in CONTAINS section at (1) temp.f95:20:20: 20 | exit | 1 Error: EXIT statement at (1) is not within a construct temp.f95:21:15: 21 | end if | 1 Error: Expecting END MODULE statement at (1) temp.f95:22:11: 22 | end do | 1 Error: Expecting END MODULE statement at (1) temp.f95:23:7: 23 | end function maxUnitsOnTruck | 1 Error: Expecting END MODULE statement at (1) temp.f95:27:9: 27 | use MaxUnitsOnTruck | 1 Fatal Error: Cannot open module file ‘maxunitsontruck.mod’ for reading at (1): No such file or directory compilation terminated.
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.
arrival
array. For each request, dequeue any servers that have finished processing their tasks, and enqueue them into availableServers
.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.serverRequests
to find the maximum count (i.e. the highest number of requests handled).#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.
arrival
array. For each request, dequeue any servers that have finished processing their tasks, and enqueue them into availableServers
.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.serverRequests
to find the maximum count (i.e. the highest number of requests handled).