Course contentsShow
← Computer Science
Lesson 899 of 2,87221. Greedy AlgorithmsFree lesson

Connect N Ropes with Minimum Cost

Minimize cost of connecting ropes by always connecting the two shortest ropes first using a min-heap.

Connect N Ropes with Minimum Cost

You'll learn how to minimize the total cost of combining multiple ropes by always choosing the two shortest ones first.

The Problem

Imagine you have several ropes of different lengths, and you need to connect them all into one long rope. Each time you tie two ropes together, the cost equals the sum of their lengths. Your goal: minimize the total cost across all connections.

Why Greedy Works Here

The key insight is that shorter ropes should be combined early and often. If you combine two long ropes first, you pay a high cost and create an even longer rope that will add to future costs. By always picking the two shortest ropes, you ensure smaller values get "reused" in subsequent combinations.

Example: Ropes of length [4, 3, 2, 6]

  • Combine 2 + 3 = 5, cost = 5, ropes now [4, 5, 6]
  • Combine 4 + 5 = 9, cost = 9, ropes now [6, 9]
  • Combine 6 + 9 = 15, cost = 15
  • Total cost = 5 + 9 + 15 = 29

If you'd started with 4 + 6 = 10, the total would be higher!

The Min-Heap Strategy

Use a min-heap (priority queue) to efficiently always grab the two smallest ropes:

  1. Insert all rope lengths into a min-heap
  2. Extract the two minimum ropes
  3. Add their sum to the total cost
  4. Insert the combined rope back into the heap
  5. Repeat until one rope remains

This greedy choice guarantees optimal substructure: the best way to combine N ropes includes the best way to combine the first two smallest.

Key Takeaway: Connect N ropes with minimum cost by repeatedly extracting and combining the two shortest ropes using a min-heap—each greedy choice builds toward the global optimum.