Problem Statement:
You are given n ropes of different length.
You need to connect these ropes into one rope.
The cost of connecting two ropes is equal to the sum of their lengths.
Example
Input : {4, 3, 2, 6}
Output: 29
Connect 2, 3 resultant array {4, 6, 5}
Next connect 4, 5 resultant array {6, 9}
Next connect 6, 9 resultant array {29}.
Solution
We create a min-heap and insert all lengths into the min-heap
Then extract the minimum and second minimum from min heap and add them and then into min-heap.
Then maintain a variable for total cost and keep increment it.
Solution in C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
int get_min_cost(vector<int> &arr, int n)
{
priority_queue<int, vector<int>, greater<int> > pq(arr.begin(), arr.end());
int res = 0;
while (pq.size() > 1)
{
int first = pq.top();
pq.pop();
int second = pq.top();
pq.pop();
res += first + second;
pq.push(first + second);
}
return res;
}
int main()
{
vector<int> arr = { 5, 4, 2, 8};
int size = arr.size();
cout << "The min cost is " << get_min_cost(arr, size)<<endl;
return 0;
}
Output:
The min cost is 36
–