For each i in the way, you need to calculate number of empty spaces. The optimal solution is that range of size of the truck where this number is maximum. So, you need to do two tasks:
- Add each given range[l…r] with 1 (calculating number of blank spaces).
- Find out the maximum value with range of size of the truck.
For 1 you can use BIT/Segment tree but since the value to be added is known beforehand (1 in this case), there is a faster method. You can take an array ‘a’ initilised to 0 and incrementing a[l] and decrement a[r+1] for every range. After doing the prefix sum of this array you’re left with updated indices.
for 2nd part you can further take the prefix sum of previously generated array and check the maximum sum of range of size k.
You may have a look on my solution for this same approach here :
Hope it helps