Connect ropes
Repeatedly combine the two shortest ropes to minimize cumulative connection cost. About 8 minutes.
The rope connection cost
Suppose you have ropes of lengths 1, 2 and 4, and joining two ropes costs their combined length. If you connect 2 and 4 first (cost 6), then join 1 (cost 7), the total cost is 13. But if you connect 1 and 2 first (cost 3), then the 4 (cost 7), the total is only 10.
Long ropes that get joined early are paid for again and again, so join the short ones first.
- cost
- 5
Pop the two shortest: 2 and 3. Joining them costs 5.
Why a min-heap fits perfectly
Every turn, you must find and remove the two smallest numbers, and insert one new combined number. Sorting after every combine would be slow, and with many ropes that adds up quickly.
With a min-heap, each turn takes only about log n steps, so the whole job is fast: the heap keeps the shortest ropes at the top for you.
import heapq
if len(ropes) <= 1:
return 0
heapq.heapify(ropes)
total = 0
while len(ropes) > 1:
a = heapq.heappop(ropes)
b = heapq.heappop(ropes)
total += a + b
heapq.heappush(ropes, a + b)
return totalFor ropes of lengths [1, 8, 3, 5], which two ropes should you connect first?
- A1 and 3
- B5 and 8
- C1 and 8
Show the answer
1 and 3. 1 and 3 are the two smallest lengths, incurring the minimum immediate cost of 4.
Connect ropes
You are given an array ropes where ropes[i] is the length of the i-th rope. You can connect two ropes of lengths x and y into one rope at a cost of x + y. Return the minimum total cost to connect all ropes into one single rope. If there is only 0 or 1 rope, the cost is 0.
ropes = [4, 3, 2, 6] → 29
0 ≤ ropes.length ≤ 100,000 · 1 ≤ ropes[i] ≤ 100,000 · the total can pass 2^31, so keep it in a 64-bit integer