Connect `n` ropes with minimal cost
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,
Output: The minimum cost is 36
[5, 4, 2, 8] –> First, connect ropes of lengths 4 and 2 that will cost 6.
[5, 6, 8] –> Next, connect ropes of lengths 5 and 6 that will cost 11.
[11, 8] –> Finally, connect the remaining two ropes that will cost 19.
Therefore, the total cost for connecting all ropes is 6 + 11 + 19 = 36.
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 are left with a single rope.
At each iteration of the loop, we will 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 41 |
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 total = x + y # insert the cost back to the min-heap heappush(prices, total) # update the minimum cost cost += total return cost if __name__ == '__main__': prices = [5, 4, 2, 8] print('The minimum cost is', findMinCost(prices)) |
Output:
The minimum cost is 36
The time complexity of the above solution is O(n.log(n)) and requires O(n) extra space, where n is the total number of ropes.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)