求指定负载运输的最小成本 优化高时间复杂度解法

问题描述 #

现有m辆卡车用于运输负载，每辆卡车仅在Left[i]至Right[i]时段可用，具备Capacity[i]的运输容量，运输成本为Cost[i]。给定n天的运输需求，每天需运输容量为k的负载，求完成运输的最小总成本。

示例 #

n = 5 天
k = 7 （每日所需运输容量）
trucks = [[1,3,5,2], [1,4,5,3], [2,5,10,1]]，数组元素依次为 Left、Right、Capacity、Cost

答案：

44

解释：

trucks[0] = [1,3,5,2]：可用时段为第1-3天，容量5，每单位成本2
每日需运输容量k=7，共5天：
a) 第1天：可用卡车为trucks[0]和trucks[1]，优先选成本最低的trucks[0]（成本2），用它运5单位，剩余2单位用trucks[1]（成本3），总成本5*2 + 2*3 = 16
b) 第2天：选trucks[2]（可用时段2-5天，容量10，成本1），运7单位，成本7*1=7
c) 第3天：同样选trucks[2]，成本7*1=7
d) 第4天：同样选trucks[2]，成本7*1=7
e) 第5天：同样选trucks[2]，成本7*1=7
总费用：16+7+7+7+7=44

约束条件 #

n 和 m 的范围为1到10^4
保证每天都有足够卡车完成当日运输需求

原解法及问题 #

原解法思路：

遍历每一天（1到n）：
    遍历所有卡车，筛选出当日可用的卡车，放入按成本降序排列的优先队列
    从队列中依次取出卡车，计算当日运输成本

该解法时间复杂度为O(nmm)，对于n和m均为1e4的场景，计算效率极低，必须优化。

优化方案 #

核心思路：事件驱动+最小堆 #

避免每天重复遍历所有卡车，通过事件触发管理卡车的可用状态变化，同时维护一个按单位成本升序的最小堆（优先选用最便宜的卡车），大幅减少冗余计算。

具体步骤 #

1. 预处理卡车事件

   • 将每辆卡车拆分为两个事件：
     • 「加入事件」：在Left[i]当天，将该卡车加入可用队列
     • 「退出事件」：在Right[i]+1当天，标记该卡车为不可用（Right[i]是最后可用日，次日失效）
   • 将所有事件按日期排序，日期相同时，优先处理「退出事件」，避免当日加入的卡车被误移除。

2. 维护可用卡车最小堆

   • 使用最小堆存储卡车的剩余容量和单位成本，堆顶始终是当前最便宜的有效卡车
   • 用哈希表记录已过期卡车的状态，或在堆元素中附带有效截止日期，方便后续清理无效卡车

3. 按天处理运输需求
   从第1天到第n天依次执行：
   a. 处理当日所有事件：先执行「退出事件」标记过期卡车，再执行「加入事件」将卡车加入堆
   b. 清理堆顶无效卡车：循环弹出堆顶已过期或容量耗尽的卡车，直到堆顶为有效卡车
   c. 满足当日运输需求：

   • 取出堆顶最便宜的卡车，计算可使用容量（取卡车剩余容量与当日剩余需求的最小值）
   • 累加成本：使用容量 × 单位成本
   • 若卡车剩余容量耗尽则弹出堆，否则更新剩余容量后放回堆
   • 重复操作直到当日需求k被满足

时间复杂度分析 #

• 事件预处理：O(m log m)（排序m个事件）
• 堆操作：每辆卡车最多入堆、出堆各一次，每次堆操作耗时O(log m)，总堆操作成本O(m log m)
• 每日遍历：O(n)
• 整体时间复杂度：O(m log m + n log m)，完全适配n和m为1e4的场景

关键细节 #

• 事件处理顺序必须先退后进，避免逻辑错误
• 堆中卡车的剩余容量需实时更新，防止重复使用已耗尽的资源
• 过期卡车的标记要高效，避免堆中堆积大量无效元素

内容的提问来源于stack exchange，提问作者Learner