2016 ICPC World Finals L题算法优化咨询：现有解法是否最优？

最近在做2016 ICPC全球总决赛L题的作业，已经写出了能正确运行的程序，但总好奇有没有更优、更快的算法，来请教大家～

问题回顾 #

需对n块硬盘进行格式化，硬盘i格式化后容量将从a_i GB变为b_i GB。所有硬盘初始均存满数据。格式化硬盘x时，可购买额外硬盘存储其数据，已格式化的硬盘若有剩余容量也可用于存储，且数据可拆分。需编写程序计算格式化所有硬盘且不丢失数据所需的最小额外空间。

当前使用的算法 #

我现在用的算法步骤如下：

• 先把硬盘分成两类：格式化后容量减少的（我叫它shrink list）、容量维持或增加的（叫grow list）
• 对两个列表分别排序：shrink list按初始容量降序排列，grow list按初始容量升序排列
• 从grow list的第一个硬盘开始，把它的初始容量赋值给swap（用来记录累计需要的交换空间），把它格式化后的容量增量（b_i - a_i）赋值给extra（记录已格式化硬盘能提供的额外可用容量，初始值至少为0）
• 接下来先遍历完grow list的所有硬盘，再处理shrink list：
  1. 检查swap + extra是否大于等于待格式化硬盘x的初始容量a_x：
     • 如果满足条件，直接格式化x即可
     • 如果不满足，就需要增大swap直到swap + extra ≥ a_x，这部分新增的swap就是需要额外购买的空间
  2. 把硬盘x的容量变化值（b_x - a_x）加到extra里
• 最终的swap就是我们需要的最小额外空间

我的疑问 #

想请教各位大佬，针对这个问题有没有更优、时间复杂度更低的解法？

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