Solution:
def maximumUnits(boxTypes, truckSize):
[Link](key=lambda x: x[1], reverse=True)
totalUnits = 0
for numBoxes, unitsPerBox in boxTypes:
if truckSize == 0:
break
boxesToTake = min(numBoxes, truckSize)
totalUnits += boxesToTake * unitsPerBox
truckSize -= boxesToTake
return totalUnits
boxTypes = [[1, 3], [2, 2], [3, 1]]
truckSize = 4
print(maximumUnits(boxTypes, truckSize)) # Output: 8
boxTypes = [[5, 10], [2, 5], [4, 7], [3, 9]]
truckSize = 10
print(maximumUnits(boxTypes, truckSize)) # Output: 91
Time and Space Complexity:
● Time Complexity: Sorting the boxtTypes array takes O(nlogn), where n is the length of
boxTypes. After sorting, we iterate over the array once, which is O(n). So, the overall
time complexity is O(nlogn).
● Space Complexity: The space complexity is O(1) since we are not using any additional
data structures apart from the input, except for a few variables to hold intermediate
results.
Solution:
def maxDisjointIntervals(A):
[Link](key=lambda x: x[1])
count = 0
last_end = -float('inf')
for start, end in A:
if start >= last_end:
count += 1
last_end = end
return count
A = [[1, 4], [2, 3], [4, 6], [8, 9]]
print(maxDisjointIntervals(A)) # Output: 3
A = [[1, 9], [2, 3], [5, 7]]
print(maxDisjointIntervals(A)) # Output: 2
Time and Space Complexity:
● Time Complexity:
○ Sorting the intervals takes O(NlogN), where N is the number of intervals.
○ The iteration through the intervals takes O(N).
○ Thus, the overall time complexity is O(NlogN)).
● Space Complexity:
○ The space complexity is O(1)) if we consider the input list as part of the input
space.