There is a flute with s holes of 1 unit each. Unfortunately n holes are imprefect and need to be covered with the help of an infintely long tape. The imprefect holes h are given in ascending order. There is a catch, you can only use a maximum of k cuts from the tape to cover the imperfect holes in the flute. While covering imperfect holes you can also cover perfect holes if need be.
Find the minimum tape length that is required to patch the flute.
Example:
Input:
s = 100, n = 4, k = 2
h = [20, 30, 75, 80]
Output:
17
Explanation:
One cut to cover holes 20 and 30, tape length = 11
One more cut to cover holes 75 and 80, length = 6
Total length = 11 + 6 = 17Comments (7)