Can anyone just say how to solve this problem. I am not asking for code just a way to solve.
There is are m cabins numbered from 1 to m where n cabins are broken. You are provided with infinitely long tape which you are allowed to cut only k times. The task is to cover all the broken cabins with minimum length of tape used. You are provided with broken cabin positions, you are also allowed to cover non-broken cabins, and it is possible that some pieces of tape will overlap.
First line contains three inputs n, m and k where n is number of cabins broken, m is total number of cabins, and k is number of tape pieces to be cut.
Second line contains n integers b1, b2, b3 ...... bn represents positions of broken cabins in increasing order.
print minimum total length of the pieces.
4 100 2
20 30 75 80
4 broken cabins, you need to cover broken cabins with 2 pieces of tape.
cabins - Bold numbers are broken cabins
length of tape used to cover cabin 20 and 30 is 11
length of tape used to cover cabin 75 and 80 is 6
so total length is 17
If k=4 that means only 1 meter tape of 4 pieces are required to cover cabins 20, 30, 75, and 80 So the total length required is 4.
I tried in many different ways by taking gaps between the broken cabins and by sorting them, but some cases are not getting solve. Please anyone just suggest algorithm to solve this problem. It is not urgent so you can take time to solve.