找出承载负载的最小成本

Question

我有

m

卡车来运载货物，指定卡车仅在

Left[i] to Right[i]

起的指定日期可用，卡车容量表示为

Capacity[i]

并收取一定金额，表示为

Cost[i]

所以每辆卡车都有4个参数，天数表示为

Left[i] to Right[i] with Capacity[i] and Cost[i]

对于给定的

n

天作为输入，我需要每天携带容量为

k

的负载，找到使用卡车运输负载的最低成本。

示例：

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

答案：

44

说明：

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

限制：

n and m range is 1 to 10^4
Also we always have enough trucks to carry the load for a particular day

这是我的代码：

static long solve(int n, int k, int[][] trucks) {
    long result = 0;

    int m = trucks.length;
    // Loop from days 1 to n

    for (int day = 1; day <= n; day++) { // O(n)
        long cost = 0;
        // sort the trucks by price
        Queue<int[]> validTrucks = new PriorityQueue<>((p, q) -> {
            return p[3] - q[3];
        });
        // loop through all trucks
        for (int j = 0; j < m; j++) { // O(m)
            int[] truck = trucks[j];
            int left = truck[0], right = truck[1];
            // check if left and right are valid range
            if (left <= day) {
                if (right >= day) {
                    // Add the queue
                    validTrucks.add(truck);
                }
            }
        }
        // find the cost for current day
        int dayCapacity = k;
        while (validTrucks.size() > 0) { // O(m)
            int[] truck = validTrucks.poll();
            int capacity = truck[2], truckCost = truck[3];
            int cap = capacity;
            if (dayCapacity < cap) {
                cap = dayCapacity;
                dayCapacity = 0;
            } else {
                dayCapacity -= capacity;
            }
            cost += truckCost * cap;

        }
        result += cost;
    }
    return result;
}

我的代码的时间复杂度为

O(n*m*m)

，如何在更短的时间内解决这个问题？

Answer 1

你从哪里得到

O(n*m²)

的？我看到一个

O(n*m*log(m))

n-times O(n*...)
  sort-by-m O(mlog(m))
  iterate-over-m //O(m), irrelevant, dominated by previous

可以降低到

O(n*m+m*log(m))

sort trucks by cost ascending O(m*log(m))
make a int sums[n] table initialized to zero
for each truck: O(m*...)
  for i from left to right: O(n)
    if sums[i] < k: sums[i]+=truck cost
sum the sums table and return//O(n), irrelevant