DiffPush Tier Heaps · Hard Problems O(n log n) · O(n)
A utility crew must splice a pile of cables into one continuous line. Every splice fuses two runs into one whose length is the sum, and the work order charges exactly that sum per splice. Because an early fat splice keeps getting re-spliced later, joining the two shortest runs at every step keeps total spend minimal. Compute the cheapest possible bill.
Input: An integer array arr of rope lengths.
Output: Return the minimum total cost to join all ropes into one.
1 <= arr.length <= 10^41 <= arr[i] <= 10^4Input: {"arr":[4,3,2,6]}
Output: 29
Splice 2+3=5, then 4+5=9, then 6+9=15; the bill totals 29.
Input: {"arr":[1,2,3,4,5]}
Output: 33
Splices are 1+2=3, 3+3=6, 4+5=9 and 6+9=15 — bills of 3, 6, 9, 15 totalling 33.