Sponsored
This approach involves sorting the box types by the number of units per box in descending order. Once sorted, the boxes are loaded onto the truck with the highest units per box first, maximizing the number of units on the truck until it reaches its capacity.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) extra space, as we sort in place.
1#include <stdio.h>
2#include <stdlib.h>
3
4int compare(const void* a, const void* b) {
5 int* boxA = *(int**)a;
6 int* boxB = *(int**)b;
7 return boxB[1] - boxA[1];
8}
9
10int maximumUnits(int** boxTypes, int boxTypesSize, int* boxTypesColSize, int truckSize) {
11 qsort(boxTypes, boxTypesSize, sizeof(int*), compare);
12 int totalUnits = 0;
13 for (int i = 0; i < boxTypesSize; ++i) {
14 int boxesToTake = fmin(boxTypes[i][0], truckSize);
15 totalUnits += boxesToTake * boxTypes[i][1];
16 truckSize -= boxesToTake;
17 if (truckSize == 0) {
18 break;
19 }
20 }
21 return totalUnits;
22}This solution sorts the boxTypes array based on the units per box in descending order. Then, it iterates through the sorted array, adding as many boxes as possible from each type to the truck until the truck's capacity is reached. The function returns the total units accumulated.
Instead of sorting by each unit's count, employ counting sort principles to store the total units in an array where the index represents the units per box. This could potentially be faster for large inputs with many boxes and limited unit types.
Time Complexity: O(n + M) where M = 1000 is a constant.
Space Complexity: O(M) for the counting array.
1#include <vector>
using namespace std;
#define MAX_UNITS 1000
class Solution {
public:
int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
vector<int> count(MAX_UNITS + 1, 0);
for (const auto& box : boxTypes) {
count[box[1]] += box[0];
}
int totalUnits = 0;
for (int i = MAX_UNITS; i > 0 && truckSize > 0; --i) {
if (count[i] > 0) {
int boxesToTake = min(truckSize, count[i]);
totalUnits += boxesToTake * i;
truckSize -= boxesToTake;
}
}
return totalUnits;
}
};The C++ solution employs a counting approach focusing on unit counts, and incrementally takes maximum units based on the counting index.