Add Petrol Pumps To Minimize The Largest Gap
Existing petrol pumps sit at fixed kilometre markers along a national highway. You can add k new pumps anywhere between them. Place them to minimize the largest distance between adjacent pumps.
Problem
Given a sorted array stations of existing pump positions and an integer k (new pumps to add), return the minimum possible value of the maximum gap between adjacent pumps after insertion. Answers within 1e-6 of the true value are accepted.
Input
A sorted array stations of doubles/integers and an integer k.
Output
The minimized maximum adjacent gap as a floating-point number.
Constraints
- 2 ≤ stations.length ≤ 2000
- 0 ≤ stations[i] ≤ 1e8
- stations is strictly increasing.
- 1 ≤ k ≤ 1e6
Examples
Example 1
Input
stations=[1,2,3,4,5,6,7,8,9,10] k=9
Output
0.50000
Adding 9 pumps lets every gap of size 1 be halved to 0.5.
Example 2
Input
stations=[23,24,36,39,46,56,57,65,84,98] k=1
Output
14.00000
Splitting the largest gap (28, between 56 and 84? actually 65→84=19, 39→46=7) gives 14.