Minimum Cost of ropes, Time Complexity O(nlogn), GFG, Leetcode

 Statement - 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. The task is to connect the ropes with minimum cost.

Test Case -

Input:
n = 4
arr[] = {4, 3, 2, 6}
Output: 
29

Problem Link - Click

Code - using Min Heap, time complexity O(nlogn), Space Complexity O(n).

#define ll long long int

long long minCost(long long arr[], long long n) {

    // Your code here

   priority_queue<ll, vector<ll>, greater<ll>> pq;

   for(int i = 0; i < n; i++)

   {

       pq.push(arr[i]);

   }

   if(n == 1)

   {

    return 0;

   }

   ll ans = 0;

   while(pq.size() > 1)

   {

            ll a = pq.top();

            pq.pop();

            ll b = pq.top();

            pq.pop();

            pq.push(a + b);

            ans += (a+b);

   }

   return ans;

}

OFFers for You