Find the minimum cost to connect ropes in the following scenario. Given n
ropes of different lengths, we need to connect these ropes into one rope. We can connect only 2 ropes at a time. The cost required to connect 2 ropes is equal to the sum of their lengths. The length of this connected rope is also equal to the sum of their lengths. This process is repeated until n
ropes are connected into a single rope. Find the min possible cost required to connect all ropes.
Example 1:
Input: ropes = [8, 4, 6, 12]
Output: 58
Explanation: The optimal way to connect ropes is as follows
1. Connect the ropes of length 4 and 6 (cost is 10). Ropes after connecting: [8, 10, 12]
2. Connect the ropes of length 8 and 10 (cost is 18). Ropes after connecting: [18, 12]
3. Connect the ropes of length 18 and 12 (cost is 30).
Total cost to connect the ropes is 10 + 18 + 30 = 58
Example 2:
Input: ropes = [20, 4, 8, 2]
Output: 54
Example 3:
Input: ropes = [1, 2, 5, 10, 35, 89]
Output: 224
Example 4:
Input: ropes = [2, 2, 3, 3]
Output: 20
Solution
Time complexity: O(nlogn).
Space complexity: O(n).
C++ solution for the problem is as follows:
// constructing priority queues | |
#include <iostream> // std::cout | |
#include <queue> // std::priority_queue | |
#include <vector> // std::vector | |
#include <functional> // std::greater | |
int ConnectRopes(std::vector<int> vecInput) | |
{ | |
int result = 0; | |
std::priority_queue<int, std::vector<int>, std::greater<int> > | |
connectEdges(vecInput.begin(), vecInput.end()); | |
int interimResult = 0; | |
while (!connectEdges.empty()) | |
{ | |
int minFirst = connectEdges.top(); | |
int minSecond = 0; | |
connectEdges.pop(); | |
if (!connectEdges.empty()) | |
{ | |
minSecond = connectEdges.top(); | |
connectEdges.pop(); | |
} | |
int addUp = minFirst+minSecond; | |
interimResult += addUp; | |
if(connectEdges.size() != 0) | |
connectEdges.push(addUp); | |
} | |
return interimResult; | |
} | |
int main() | |
{ | |
std::vector<int> vecIn = {2,2,3,3};// { 1, 2, 5, 10, 35, 89 }; //{8, 4, 6, 12};// | |
std::cout<< ConnectRopes(vecIn); | |
return 0; | |
} |
Check out more algorithms here.
Reference:
This problem was found in LeetCode.