Greedy: Connect ropes with minimum cost.

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

 

 

 

Write a Comment

Leave a Comment

Your email address will not be published. Required fields are marked *