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.
1using System;
2
3public class Solution {
4 public int MaximumUnits(int[][] boxTypes, int truckSize) {
5 Array.Sort(boxTypes, (a, b) => b[1] - a[1]);
6 int totalUnits = 0;
7 foreach (var box in boxTypes) {
8 int boxesToTake = Math.Min(box[0], truckSize);
9 totalUnits += boxesToTake * box[1];
10 truckSize -= boxesToTake;
11 if (truckSize == 0) break;
12 }
13 return totalUnits;
14 }
15}The C# solution sorts the array based on descending units and iteratively selects box types for the maximum unit count.
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 private const int MAX_UNITS = 1000;
public int MaximumUnits(int[][] boxTypes, int truckSize) {
int[] count = new int[MAX_UNITS + 1];
foreach (var box in 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 = Math.Min(truckSize, count[i]);
totalUnits += boxesToTake * i;
truckSize -= boxesToTake;
}
}
return totalUnits;
}
}The C# solution uses a counting mechanism to prioritize and fill the truck by available unit amounts in descending order.