Finding minimum length of tape required.

Padala Vamsi ujpNQUXGRi

Can anyone just say how to solve this problem. I am not asking for code just a way to solve.

Question:
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.

Input Format
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.

Output Format
print minimum total length of the pieces.

Example:
Input
4 100 2
20 30 75 80

Output
17

Explanation:
4 broken cabins, you need to cover broken cabins with 2 pieces of tape.
cabins - Bold numbers are broken cabins
1.......20........30....................75.......80........100
..........-----11-----___________ -----6-----_______
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.

avan

Hey @Padala-Vamsi-ujpNQUXGRi

Thank you for posting on my platform. This topic seems to somewhat be floating around the net.
Here are some of the places this topic or similar ones are being mentioned:

(Exact) https://www.codeproject.com/Questions/5294427/Finding-minimum-length-of-tape-required
(Similar) https://leetcode.com/discuss/interview-question/972598/HashedIn-or-OA-or-Min-Tape-Length/792614

I have come up with a recursive solution but I DON'T know if it's right. I wish we had more test cases so I could make sure.

The idea is this:

You loop through all the broken cabins and place the end of the first tape encompassing all broken cabins before it and then make a recursive call for the remaining cabins
If the total length is less than the minimum length update the minimum length
At the end return the minimum length

Below is the (Java) code in case my vague explanation above is not enough. Keep in mind this has not been tested extensively and could definitely be wrong. I wish we had an official leetcode challenge where I could run my code...but oh well.

SPACE INTENTIONALLY LEFT BLANK

public static int minTape(int numBrokenCabins, int totalCabins, int numTapeCuts, int[] brokenCabins){
	    int firstCabin = brokenCabins[0];
	    int maxLength =  brokenCabins[brokenCabins.length-1] - firstCabin + 1;
	    int minLength = maxLength;
	    
	    // Base cases
        if(numTapeCuts == 1){
            return maxLength;
        }
        if(numTapeCuts == numBrokenCabins){
            return numBrokenCabins;
        }
        
        for(int i = 0; i < brokenCabins.length-1; i++){
            int currentCabin = brokenCabins[i];
            int thisLength = currentCabin - firstCabin + 1;
            int newNumBrokenCabins = numBrokenCabins - i - 1;
            int newTotalCabins = totalCabins;
            int newNumTapeCuts = numTapeCuts - 1;
            int[] newBrokenCabins = Arrays.copyOfRange(brokenCabins, i+1, brokenCabins.length);
            if(newNumBrokenCabins < newNumTapeCuts){
                break;
            }
            int totalLength = thisLength + minTape(newNumBrokenCabins, newTotalCabins, newNumTapeCuts, newBrokenCabins);
            minLength = totalLength < minLength ? totalLength : minLength;
        }
        
        return minLength;
	}

View and Run Code Online

Please let me know if you find a mistake or if it fails for a specific case. I would love a chance to fix my code. Thank you.

avan