Minimize Max Distance to Gas Station

hard binary-search search math

Problem

Given sorted station positions and K additional stations to place, minimize the maximum distance between adjacent stations.

Inputstations=[1,2,3,4,5,6,7,8,9,10], K=9

Output0.500000

With nine extra stations placed at midpoints, the max gap becomes 0.5.

input

def minmaxGasDist(stations, K):
    lo, hi = 0.0, stations[-1] - stations[0]
    for _ in range(60):
        mid = (lo + hi) / 2
        need = 0
        for i in range(1, len(stations)):
            need += int((stations[i] - stations[i-1]) / mid)
        if need > K: lo = mid
        else: hi = mid
    return hi

function minmaxGasDist(stations, K) {
  let lo = 0, hi = stations[stations.length-1] - stations[0];
  for (let it = 0; it < 60; it++) {
    const mid = (lo + hi) / 2;
    let need = 0;
    for (let i = 1; i < stations.length; i++)
      need += Math.floor((stations[i] - stations[i-1]) / mid);
    if (need > K) lo = mid; else hi = mid;
  }
  return hi;
}

double minmaxGasDist(int[] stations, int K) {
    double lo = 0, hi = stations[stations.length-1] - stations[0];
    for (int it = 0; it < 60; it++) {
        double mid = (lo + hi) / 2;
        int need = 0;
        for (int i = 1; i < stations.length; i++)
            need += (int)((stations[i] - stations[i-1]) / mid);
        if (need > K) lo = mid; else hi = mid;
    }
    return hi;
}

double minmaxGasDist(vector<int>& stations, int K) {
    double lo = 0, hi = stations.back() - stations.front();
    for (int it = 0; it < 60; it++) {
        double mid = (lo + hi) / 2;
        int need = 0;
        for (int i = 1; i < (int)stations.size(); i++)
            need += (int)((stations[i] - stations[i-1]) / mid);
        if (need > K) lo = mid; else hi = mid;
    }
    return hi;
}

Explanation

We want the smallest possible value for the largest gap between adjacent stations after adding K new ones. Since "can we achieve a max gap of D?" gets easier as D grows, we binary-search the answer D directly (on real numbers).

For a candidate gap D, each existing gap of width w needs floor(w / D) extra stations to be cut into pieces no longer than D. Summing this over all gaps gives the total stations need required.

If need > K we do not have enough stations, so D is too small and we raise lo. Otherwise D is achievable and we lower hi. Because the answer is a real number, we just run a fixed number of iterations (here 60) to converge to high precision instead of stopping on equality.

Example: stations = [1..10] with K = 9. Each of the 9 unit gaps can take one extra station at its midpoint, halving every gap to 0.5, which is the minimized maximum distance.

Each feasibility check scans the gaps once, and 60 halving steps shrink the search interval to a tiny range, giving the answer accurately.

Time: O(n log(1/eps)) Space: O(1)