Connect Ropes With Minimum Cost
Intermediate
You have ropes with lengths ropes[i]. Joining two ropes costs the sum of their lengths and gives one rope of that length. Join all the ropes into one, and return the minimum total cost.
For [4, 3, 2, 6] the answer is 29 (join 2+3 = 5, then 4+5 = 9, then 6+9 = 15; total 5 + 9 + 15 = 29).
The starter code re-sorts the ropes after every join. It is correct but too slow for many ropes.
Examples
Example 1
Input:
connect_ropes([4, 3, 2, 6])
Output:
29
Example 2
Input:
connect_ropes([1, 2, 3, 4, 5])
Output:
33
Constraints
0 <= len(ropes) <= 1000001 <= ropes[i] <= 10**4
Theory
Go to TheoryKeywords
dsa-sheetheapsheap-basics
Run your code to see results
No results yet
Run your code to check it against the examples, or submit to run every test.