pg

There are given n ropes of different lengths, we need to connect these ropes into one rope. The cost to connect two ropes is equal to sum of their lengths. We need to connect the ropes with minimum cost.

For example if we are given 4 ropes of lengths 4, 3, 2 and 6. We can connect the ropes in following ways.
1) First connect ropes of lengths 2 and 3. Now we have three ropes of lengths 4, 6 and 5.
2) Now connect ropes of lengths 4 and 5. Now we have two ropes of lengths 6 and 9.
3) Finally connect the two ropes and all ropes have connected.

Total cost for connecting all ropes is 5 + 9 + 15 = 29.

We can see that the results of previous picked ropes will include more than once in the whole process.
So we need to use greedy algorithm by picked smallest ropes every time.
And the result needs to be added into current array.
Then choose two smallest numbers again.

So we need to build a min heap.

The easiest way to build a min heap by C++ and java is using priority queue.

1
2
3
4
5
6
7
8
9
10
11
12
13

int minCost(vector<int>& ropes){
    priority_queue<int, vector<int>, greater<int>> pq;
    int res = 0;
    for(int r : ropes)
        pq.push(r);
    while(pq.size() > 1){
        int len1 = pq.top(); pq.pop();
        int len2 = pq.top(); pq.pop();
        res += len1 + len2;
        pq.push(len1+len2);
    }
    return res;
}