我有m辆卡车要装载，一辆给定的卡车只在提到的Left[i] to Right[i]天内可用，卡车容量表示为Capacity[i]，并收取一些金额表示为Cost[i]
因此每辆卡车有4个参数，天数表示为Left[i] to Right[i] with Capacity[i] and Cost[i]
对于给定的n天作为输入，我需要进行负载的能力k对每一天，找到最低成本运输负载使用卡车.
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
这是我的做法:
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.
我的代码有O(n*m*m)的时间复杂度，如何在更短的时间内解决这个问题？