Description
Add k gas stations to minimize the maximum distance between adjacent stations. Return the answer with 10^-6 precision.
Examples
Input:
stations = [1,2,3,4,5,6,7,8,9,10], k = 9Output:
0.5Explanation:
Add stations to halve max distance.
Input:
stations = [1], k = 9Output:
0.5Explanation:
Edge case with a single-element array.
Input:
stations = [1, 5, 10], k = 4Output:
2.0Explanation:
Initially the gaps are [4, 5]. The maximum gap is 5. With 4 stations to add, 2 stations divide the gap [5,10] into 3 parts of ~1.67 each, and 2 stations divide the gap [1,5] into 3 parts of ~1.33 each. The maximum distance is minimized to approximately 1.67.
Constraints
- •
2 ≤ stations.length ≤ 10⁵