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

Tested only

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;
}

Reflection

Which cue made you pick this pattern in under 90 seconds?
What input would break a wrong invariant?