Intermediate Level
Implement the minimumCostConnectRopes method that returns the minimum total cost needed to connect all ropes.
The input array ropes contains the lengths of size ropes.
Your task is to connect all ropes into one rope with the minimum total cost. Whenever two ropes are connected, the cost is equal to the sum of their lengths.
For example, for [4,3,2,6], the minimum total cost is 29 when the smallest ropes are connected first.
Example 1
Input
ropes (int[]) =
[4,3,2,6]size (int) =
4Returns (int)
29Example 2
Input
ropes (int[]) =
[1,2,3,4,5]size (int) =
5Returns (int)
33Example 3
Input
ropes (int[]) =
[5]size (int) =
1Returns (int)
0Always connect the two shortest ropes first.
This greedy choice keeps future connection costs as small as possible. Use a min heap to quickly get the two smallest rope lengths each time.
After connecting two ropes, add their sum to the total cost and push the combined rope back into the heap. Continue until only one rope remains.
Pseudocode:
function minimumCostConnectRopes(ropes, size):
create minHeap from ropes
totalCost = 0
while heap size > 1:
first = remove smallest from minHeap
second = remove smallest from minHeap
cost = first + second
totalCost = totalCost + cost
push cost into minHeap
return totalCostReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run