Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Minimize Max Distance to Gas Station

Problem (restated)

Add k new gas stations on the number line (stations sorted). Minimize the maximum distance between adjacent stations.

Intuition

If max gap D is feasible with ≤k inserts, larger D is too. Binary search real-valued D.

Approaches

Binary search on max gap

Unverified

Time O(n log(1/ε))Space O(1)

Idea. For mid D, stations needed between a,b is ceil((b-a)/D)-1; sum ≤ k.

Walkthrough. stations=[1,2,3,4,5,6,7,8,9,10], k=9 → answer 0.5.

Trade-offs. Floating binary search needs epsilon; heap simulation is discrete alternative.

Solution

export function minmaxGasDist(stations: number[], k: number): number {
  let lo = 0, hi = stations[stations.length - 1]! - stations[0]!;
  const ok = (d: number) => {
    let need = 0;
    for (let i = 1; i < stations.length; i++) {
      const gap = stations[i]! - stations[i - 1]!;
      need += Math.ceil(gap / d) - 1;
    }
    return need <= k;
  };
  for (let t = 0; t < 80; t++) {
    const mid = (lo + hi) / 2;
    if (ok(mid)) hi = mid; else lo = mid;
  }
  return hi;
}

export function minmaxGasDist(stations: number[], k: number): number {
  let lo = 0, hi = stations[stations.length - 1]! - stations[0]!;
  const ok = (d: number) => {
    let need = 0;
    for (let i = 1; i < stations.length; i++) {
      const gap = stations[i]! - stations[i - 1]!;
      need += Math.ceil(gap / d) - 1;
    }
    return need <= k;
  };
  for (let t = 0; t < 80; t++) {
    const mid = (lo + hi) / 2;
    if (ok(mid)) hi = mid; else lo = mid;
  }
  return hi;
}

Template connection

Binary search on the max adjacent gap; greedy station-count is the feasibility check.

Reflection

The answer is a real number: the maximum gap you will allow. Does feasible(d) ask whether k new stations cover every gap larger than d?
The loop runs while hi - lo > eps. What does a too-coarse eps do to the accepted answer?
k = 0: the answer is the largest gap already on the road.