I have m trucks to carry load, a given truck is available only on mentioned days from Left[i] to Right[i], the truck capacity is represented as Capacity[i] and charges some amount represented as Cost[i]
So every truck has 4 parameters, day numbers represented as Left[i] to Right[i] with Capacity[i] and Cost[i]
For given n days as input and I need to carry a load of capacity k on each day, find the minimum cost to transport the load using the trucks.
Example:
n = 5 days
k = 7 capacity per day
trucks = [[1,3,5,2], [1,4,5,3], [2,5,10,1]], each item in the array represents Left, Right, Capacity and Cost
Answer:
44
Explanation:
for trucks[0] = [1,3,5,2] , it is available on days 1 to 3, with truck capacity as 5 and charges 2
I have a task to carry a capacity of k=7 for each day, with number of days as n=5
a) Day 1
Day 1, we have trucks[0] and trucks[1] but lowest cost is for trucks[0] as 2 but it has only capactity as 5
So Day 1, transport 5 items using trucks[0] and 2 items using trucks[1], so cost is 5*2 + 2*3 = 16
b) Day 2, we can pick trucks[2]=[2,5,10,1] because left=2 matches with the day we are looking for also it can carry a capacity of 10 load.
Cost for Day 2 is 7*1 = 7
c) Day 3, pick trucks[2]=[2,5,10,1] because 3 falls in range [2,5], cost for Day 3 is 7*1 = 7
d) Day 4, pick trucks[2]=[2,5,10,1] because 4 falls in range [2,5], cost for Day 3 is 7*1 = 7
e) Day 5, pick trucks[2]=[2,5,10,1] because 5 falls in range [2,5], cost for Day 3 is 7*1 = 7
Total cost for all days is = 16+7+7+7+7 = 44
Constraints:
n and m range is 1 to 10^4
Also we always have enough trucks to carry the load for a particular day
This is my approach:
Use for loop from 1 to number of days
Loop through all the trucks and select the trucks that can carry load in the required days and put them in PriorityQueue that is sorted by cost in descending order.
Next using a loop, poll items from queue, and calculate cost for given day.
My code has time complexity of O(n*m*m), how to solve this in less time?
Where did you get O(n*m²) for yours? I see a O(n*m*log(m))
n-times O(n*...)
sort-by-m O(mlog(m))
iterate-over-m //O(m), irrelevant, dominated by previous
Could be brought down to O(n*m+m*log(m))
sort trucks by cost ascending O(m*log(m))
make a int hauled[n] table initialized to zero
int cost=0
for each truck: O(m*...)
for i from left to right: O(n)
if hauled[i] < k:
cost+=truck cost
hauled[i]+=truck capacity
return cost