Minimize Max Distance to Gas Station
Hard · Binary Search · Array · Binary Search
Problem
Gas stations stand on a straight road at the positions in stations, which are strictly increasing. You must add exactly k new stations, each at any real position (it does not have to be a whole number).
The penalty is the largest distance between two neighboring stations after the additions. Return the smallest possible penalty.
The answer is a real number. It is accepted when it is within 10^-6 of the exact value (absolute or relative).
Examples
Input: stations = [0,10], k = 1 Output: 5.0
One new station at 5 leaves two gaps of 5.
Input: stations = [1,4,12], k = 2 Output: 3.0
Both stations go into the gap of 8 (pieces of about 2.667), so the untouched gap of 3 is the largest.
Input: stations = [0,3,6,9], k = 3 Output: 1.5
One station in the middle of each gap of 3 leaves pieces of 1.5.
Constraints
- 2 <= stations.length <= 2000
- 0 <= stations[i] <= 10^8
- stations is strictly increasing.
- 1 <= k <= 10^6
Approaches
- Place stations one by one — time O(k · n), space O(n)
Follow-up
A greedy also works: give each new station to the gap whose current pieces are longest, using a max-heap keyed by gap / pieces. That is O(k log n), which is slow when k is 10^6 but exact. The binary search does not depend on k at all: O(n log(maxGap / ε)).
Related problems
Start free on Cariara · Coding problems · System design studio
