Cheapest Rope Joining
Problem
A rigger has several ropes with known lengths and must splice them into one. Splicing two ropes costs the sum of their lengths and produces a rope of that combined length, which can be spliced again later. Return the smallest total cost of ending up with a single rope. With one rope or none there is nothing to splice.
Examples
Input: lengths = [4, 3, 2, 6]
Output: 29
Why: 2 + 3 = 5, then 4 + 5 = 9, then 6 + 9 = 15, and 5 + 9 + 15 = 29Input: lengths = [1, 1, 1, 1]
Output: 8
Why: two pairs cost 2 each, then the two halves cost 4Input: lengths = [8]
Output: 0
Why: edge case, already a single ropeHints
0 / 3
A rope's length is paid again every time the rope it belongs to is spliced. Which ropes should take part in the most splices?
Short ropes are cheap to carry through many splices, long ones are expensive. This is the same shape as building a Huffman code, where rare symbols sit deepest.
Put every length in a min-heap. Repeatedly pop the two shortest ropes, add their sum to the total, and push the spliced rope back, until one rope remains.
Solution
Every original rope is paid for once per splice it takes part in, so the total cost is each length times its depth in the tree of splices. Exactly as in Huffman coding, splicing the two shortest ropes first is always safe: they can be placed deepest without making any other choice worse. A min-heap hands back the two shortest ropes in O(log n), and the spliced rope goes back in as a new candidate. Time is O(n log n) and space is O(n).
import heapq
def join_cost(lengths):
heap = list(lengths)
heapq.heapify(heap)
total = 0
while len(heap) > 1:
a, b = heapq.heappop(heap), heapq.heappop(heap) # the two shortest ropes
total += a + b
heapq.heappush(heap, a + b) # the splice joins the pool
return total
print(join_cost([4, 3, 2, 6])) # -> 29
print(join_cost([1, 1, 1, 1])) # -> 8
print(join_cost([8])) # -> 0Stuck on the idea rather than the code? Huffman Intuition covers it.