Loading problem...
You are given a sorted array of integers called positions, representing the locations of existing service points (such as charging stations, distribution centers, or supply depots) along a one-dimensional highway or route. You are also given an integer k, representing the number of additional service points you can install.
You may place these new service points at any real-valued location along the route—not necessarily at integer positions. After placing all k new service points, calculate the largest gap (i.e., the maximum distance between any two consecutive service points in the final configuration).
Your goal is to minimize this largest gap. That is, strategically place the k new service points to reduce the maximum distance anyone would have to travel between adjacent service points as much as possible.
Return the minimum possible value of the largest gap after optimally placing all k new service points. Answers within 10⁻⁶ of the actual answer will be accepted.
positions = [1,2,3,4,5,6,7,8,9,10]
k = 90.50000The initial positions are evenly spaced with gaps of 1. With 9 additional placements, we can add one new point in the middle of each of the 9 gaps, reducing each gap from 1.0 to 0.5. The largest gap after optimal placement is 0.5.
positions = [23,24,36,39,46,56,57,65,84,98]
k = 114.00000The gaps between consecutive positions are: 1, 12, 3, 7, 10, 1, 8, 19, 14. The largest gap is 19 (between 65 and 84). With only 1 additional placement, we can divide this gap of 19 into two gaps of 9.5 each. However, this results in a new largest gap of 14 (between 84 and 98). Alternatively, we could place the new point to split the 14-gap, but then the 19-gap remains as the largest. The optimal strategy yields a minimum largest gap of 14.00000.
positions = [0,10,20,30,40,50,60,70,80,90]
k = 95.00000The positions are evenly spaced with gaps of 10. With 9 additional placements, we can place one new point in the middle of each of the 9 gaps, splitting each 10-unit gap into two 5-unit gaps. Thus, the minimum largest gap achievable is 5.00000.
Constraints