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 the sum of their lengths. We need to connect the ropes with minimum cost.
This approach is similar to Huffman Coding. We put the smallest ropes down the tree so that they can be repeated multiple times rather than the longer ropes.
Time Complexity: O(N log N), assuming that we use an O(N log N) sorting algorithm.
Note that heap operations like insert and extract take O(Logn) time.
Auxiliary Complexity: O(n).
The space required to store the values in min-heap
Checklist
[x] I've read the contribution guidelines.
[x] I've checked the issue list before deciding what to submit.
[x] I've edited the README.md and link to my code.
Have you read the Contributing Guidelines on Pull Requests?
Yes
Description
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 the sum of their lengths. We need to connect the ropes with minimum cost.
This approach is similar to Huffman Coding. We put the smallest ropes down the tree so that they can be repeated multiple times rather than the longer ropes.
Time Complexity: O(N log N), assuming that we use an O(N log N) sorting algorithm. Note that heap operations like insert and extract take O(Logn) time.
Auxiliary Complexity: O(n). The space required to store the values in min-heap
Checklist
README.mdand link to my code.Related Issues or Pull Requests
Issue: #7546