search

darwinrlo / public

0 stars 0 forks source link

Connect ropes with minimum cost #25

Open darwinrlo opened 4 years ago

darwinrlo commented 4 years ago

InterviewBit: Connect ropes with minimum length

darwinrlo commented 4 years ago

Every connection reduces the total count of rope segments by 1. If there are N ropes, then N-1 connections need to be made to reduce the number of rope segments to 1. We cannot do fewer or more than N-1 connections.

darwinrlo commented 4 years ago

Set C be the greedy solution. C[1] be the cost of the first connection. C[N-1] is the cost of the last connection.

Since C[1] is chosen greedily, C[1] has the lowest cost of any of the possible connections and is <= the first connection of any solution.

C[2] is chosen greedily. So given C[1], C[2] is the lowest-cost connection of the remaining options. If C[1] were chosen differently, could C[2] have been any cheaper?

C[1] was also chosen greedily, so any other choice for C[1] would have been resulted in a longer segment, which makes the available options for C[2] more expensive rather than less.

darwinrlo commented 4 years ago

Assumption: Any other choice for C[0], ..., C[i-1] would make the available choices for C[i] more expensive. Then the greedy choice is the cheapest choice for C[i].

darwinrlo commented 4 years ago

N-1 connections need to be made. Making different choices will not result in fewer or more connections being made. Making any other choice for the connections increase the cost.

Making a more expensive choice earlier only makes the current choice more expensive.

darwinrlo commented 4 years ago

Geeks for Geeks:

If we observe the above problem closely, we can notice that the lengths of the ropes which are picked first are included more than once in total cost. Therefore, the idea is to connect smallest two ropes first and recur for remaining ropes. This approach is similar to Huffman Coding. We put smallest ropes down the tree so that they can be repeated multiple times rather than the longer ropes.