Bucket Sort Solution
class Solution:
def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:
"""
main idea: bucket sort
tc O(N) sc O(1000)
"""
total_box = total_val = 0 # optimization
buckets = [0] *1001
for box, units in boxTypes:
total_box += box # optimization
total_val += units*box # optimization
buckets[units] += box
res = 0
if total_box <= truckSize: # optimization
return total_val # optimization
spaceleft = truckSize
for x in range(1000,0,-1):
usedBox = min(buckets[x], truckSize)
res += x * usedBox
truckSize -= usedBox
if truckSize == 0:
break
return res
class Solution:
"""
main idea: Greedy
tc O(NlgN) sc O(1)
"""
def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:
boxTypes.sort(key = lambda x: -x[1])
res = 0
for box, val in boxTypes:
if box <= truckSize:
res += box *val
truckSize -= box
else:
res += truckSize * val
return res
return res