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