You are using an outdated browser. Please update your browser for a better user experience.

Connecting Ropes

greedy

We are given n ropes of different lengths, we need to connect these ropes into one rope. The cost to connect two ropes is equal to the sum of their lengths. And we need to connect the ropes with minimum cost.

Example

If we are given 4 ropes of lengths 4, 3, 2, and 6, we can connect the ropes in the following ways.

1) First, connect ropes of lengths 2 and 3. Now we have three ropes of lengths 4, 6, and 5.

2) Now connect ropes of lengths 4 and 5. Now we have two ropes of lengths 6 and 9.

3) Finally connect the two ropes and all ropes have connected.

Total cost for connecting all ropes is 5 + 9 + 15 = 29. This is the optimized cost for connecting ropes.

What greedy choice will always lead to the optimal solution (minimized cost)?