Answer:
Given n ropes of different length, the task is to connect all the ropes into one. We need to connect these ropes in minimum cost. The cost of connecting two ropes is the sum of their lengths.
Eg: Given 4 ropes of length { 3, 7, 9, 4 }
We can connect the ropes in the following way:
1) First, connect the ropes of length 3 and 4. Cost of connecting these ropes is 3 + 4 = 7. Now we have ropes of length { 7, 7, 9 }
2) Then, connect the ropes with length 7 and 7. Now the cost of connecting these ropes is 7 + 7 = 14. Now we have ropes of length { 9, 14 }
3) Finally, connect the two last ropes with cost 9 + 14 = 23.
So, Total Cost of connecting these ropes in the above order is 7 + 14 + 23 = 44.
Approach
Given an array rope[] of length n, where rope[i] is the length of ith rope.
First of all, build minHeap from the given array of rope length, because we want to extract ropes with the minimum length of all in every iteration.
In each iteration:
1) Extract two ropes with minimum length from the minHeap.
2) add both the ropes (cost).
3) add the cost to the result and push cost again in the minHeap.
The main reason for selecting ropes with minimum length in each iteration is: The value that is picked first will be included in the final result more than once. Since we want the minimum cost of connecting ropes, we will pick long length ropes at a later stage to minimize its impact on our final cost.
Time Complexity
The complexity of insertion in minHeap is O(logn). Since we are building heap for n ropes, the overall complexity of building minHeap is O(nlogn).
Then in the iteration, we are extracting minimum value from minHeap and pushing the cost of connecting two ropes back to the minHeap. Extract/Insert operation from minHeap costs O(logn).
So, the Overall time complexity of the problem is O(nlogn).
Space Complexity
We are using space for storing minHeap of the ropes which is equal to the number of ropes we have. So Space complexity of the problem is O(n).
Explanation:
Code is:
int main() {
int t;
scanf("%d", &t);
while(t--) {
int count, first, second;
int result = 0;
scanf("%d", &count);
priority_queue< int, vector<int>, greater<int> > pq;
for(int i=0; i<count; i++){
int ropeLen;
scanf("%d", &ropeLen);
pq.push(ropeLen);
}
while(pq.size() > 1) {
first= pq.top(); pq.pop();
second = pq.top(); pq.pop();
result += (first+second);
pq.push(first+second);
}
cout<<result<<endl;
}
}
