Given n ropes of different lengths, connect them into a single rope with minimum cost. Assume that the cost to connect two ropes is the same as the sum of their lengths.
For example,
The idea is to connect the two lowest-cost ropes first. The resultant rope has a cost equal to the sum of the connected ropes. Repeat the process (with resultant rope included) until we’re left with a single rope.
At each iteration of the loop, we’ll be left with one less rope and the optimal cost is added to the total cost. The final cost for connecting n ropes will be minimal among all possible combinations. A priority queue implemented using min-heap is best suited for this problem. Following is the implementation of this approach in C++, Java, and Python using a min-heap:
C++
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
// Function to calculate the minimum cost to join `n` ropes into a single rope
int findMinCost(vector<int> const &prices)
{
// create a min-heap from input elements
priority_queue<int, vector<int>, greater<int>> pq(prices.begin(), prices.end());
// keep track of the minimum cost so far
int cost = 0;
// repeat till heap size is reduced to one
while (pq.size() > 1)
{
// Extract the top two elements from the min-heap
int x = pq.top();
pq.pop();
int y = pq.top();
pq.pop();
// calculate the cost of the extracted values
int sum = x + y;
// insert the cost back to the min-heap
pq.push(sum);
// update the minimum cost
cost += sum;
}
return cost;
}
int main()
{
vector<int> prices = { 5, 4, 2, 8 };
cout << “The minimum cost is “ << findMinCost(prices);
return 0;
}
|
Output:
The minimum cost is 36
Java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
class Main
{
// Function to calculate the minimum cost to join `n` ropes into a single rope
public static int findMinCost(List<Integer> prices)
{
// create a min-heap using `PriorityQueue` class from elements of the list
PriorityQueue<Integer> pq = new PriorityQueue<>(prices);
// keep track of the minimum cost so far
int cost = 0;
// repeat till heap size is reduced to one
while (pq.size() > 1)
{
// Extract the top two elements from the min-heap
int x = pq.poll();
int y = pq.poll();
// calculate the cost of the extracted values
int sum = x + y;
// insert the cost back to the min-heap
pq.add(sum);
// update the minimum cost
cost += sum;
}
return cost;
}
public static void main(String[] args) {
List<Integer> prices = Arrays.asList(5, 4, 2, 8);
System.out.println(“The minimum cost is “ + findMinCost(prices));
}
}
|
Output:
The minimum cost is 36
Python
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
import heapq
from heapq import heappush, heappop
# Function to calculate the minimum cost to join `n` ropes into a single rope
def findMinCost(prices):
# In-place transform list `prices` into a min-heap in linear time
heapq.heapify(prices)
# keep track of the minimum cost so far
cost = 0
# repeat till heap size is reduced to one
while len(prices) > 1:
# Extract the top two elements from the min-heap
x = heappop(prices)
y = heappop(prices)
# calculate the cost of the extracted values
sum = x + y
# insert the cost back to the min-heap
heappush(prices, sum)
# update the minimum cost
cost += sum
return cost
if __name__ == ‘__main__’:
prices = [5, 4, 2, 8]
print(“The minimum cost is”, findMinCost(prices))
|
Output:
The minimum cost is 36
Download Run Code
Output:
The minimum cost is 36
Download Run Code
Output:
The minimum cost is 36
Download Run Code
Output:
The minimum cost is 36The time complexity of the above solution is O(n) and requires O(n) extra space, where n is the total number of ropes.