Minimize Maximum Distance Between Gas Stations

Like20

Minimize Maximum Distance Between Gas Stations is an answer-space optimization problem on a number line. You are given sorted station positions and allowed to add k new stations at fractional coordinates. The objective is to minimize the largest gap between adjacent stations after placements are made optimally.

The accepted method is binary search on the maximum allowed gap D. For each candidate D, compute how many new stations are needed so every original gap is split into pieces no larger than D. If required stations are within budget k, D is feasible and you search smaller; otherwise search larger. Continue until numerical precision reaches the required tolerance.

Judge checks include simple two-station layouts, uneven spacing, zero-addition cases, and precision-sensitive scenarios where floating-point handling must be careful. Return a numeric answer compatible with tolerance-based comparison. Core correctness depends on monotonic feasibility and accurate station-count formulas per gap, especially for exact-divisible distances where off-by-one rounding mistakes can silently shift results.

Precision management matters: stop binary search when interval width is below tolerance, and compute required station counts with mathematically correct floor/ceil behavior per gap. Small rounding mistakes can shift feasibility decisions near boundaries, causing off-by-one station requirements and failing strict floating-point checks.

Examples

Example 1

Input

stations = [1, 2, 10], k = 2

Output

3.0

Explanation

Adding stations at positions 4 and 7 results in gaps of at most 3.

Example 2

Input

stations = [1, 2, 3, 4, 5, 6, 7, 8, 9], k = 3

Output

1.0

Explanation

Adding 3 stations evenly between existing ones can make all distances at most 1.

Example 3

Input

stations = [1, 10], k = 1

Output

4.5

Explanation

Adding one station at position 5.5 minimizes the maximum gap to 4.5.

Algorithm Flow

Recommendation Algorithm Flow for Minimize Maximum Distance Between Gas Stations - Budibadu

Best Answers

java

class Solution {
    public double minimize_max_distance(int[] stations, int k) {
        double low = 0, high = stations[stations.length - 1] - stations[0];
        for (int i = 0; i < 100; i++) {
            double mid = (low + high) / 2;
            if (check(mid, stations, k)) high = mid;
            else low = mid;
        }
        return high;
    }
    private boolean check(double d, int[] stations, int k) {
        int count = 0;
        for (int i = 0; i < stations.length - 1; i++) {
            count += (int)((stations[i+1] - stations[i]) / d);
        }
        return count <= k;
    }
}

javascript

function minimize_max_distance(stations, k) {
    function check(d) {
        let count = 0;
        for (let i = 0; i < stations.length - 1; i++) {
            count += Math.floor((stations[i+1] - stations[i]) / d);
        }
        return count <= k;
    }
    let low = 0, high = stations[stations.length - 1] - stations[0];
    for (let i = 0; i < 100; i++) {
        let mid = (low + high) / 2;
        if (check(mid)) high = mid;
        else low = mid;
    }
    return high;
}

php

function minimize_max_distance($stations, $k) {
    $check = function($d) use ($stations, $k) {
        $count = 0;
        for ($i = 0; $i < count($stations) - 1; $i++) {
            $count += floor(($stations[$i+1] - $stations[$i]) / $d);
        }
        return $count <= $k;
    };
    $low = 0; $high = $stations[count($stations) - 1] - $stations[0];
    for ($i = 0; $i < 100; $i++) {
        $mid = ($low + $high) / 2;
        if ($check($mid)) $high = $mid;
        else $low = $mid;
    }
    return $high;
}

python

def minimize_max_distance(stations, k):
    def check(d):
        count = 0
        for i in range(len(stations) - 1):
            count += int((stations[i+1] - stations[i]) / d)
        return count <= k
    
    low, high = 0, stations[-1] - stations[0]
    for _ in range(100):
        mid = (low + high) / 2
        if check(mid): high = mid
        else: low = mid
    return high

rust

pub fn minimize_max_distance(stations: Vec<i32>, k: i32) -> f64 {
    let mut low = 0.0;
    let mut high = (stations[stations.len() - 1] - stations[0]) as f64;
    for _ in 0..100 {
        let mid = (low + high) / 2.0;
        let mut count = 0;
        for i in 0..stations.len() - 1 {
            count += ((stations[i+1] - stations[i]) as f64 / mid) as i32;
        }
        if count <= k { high = mid; }
        else { low = mid; }
    }
    high
}

typescript

function minimize_max_distance(stations: number[], k: number): number {
    function check(d: number) {
        let count = 0;
        for (let i = 0; i < stations.length - 1; i++) {
            count += Math.floor((stations[i+1] - stations[i]) / d);
        }
        return count <= k;
    }
    let low = 0, high = stations[stations.length - 1] - stations[0];
    for (let i = 0; i < 100; i++) {
        let mid = (low + high) / 2;
        if (check(mid)) high = mid;
        else low = mid;
    }
    return high;
}

Comments (0)

Join the Discussion

Share your thoughts, ask questions, or help others with this problem.

Minimize Maximum Distance Between Gas Stations

Examples

Algorithm Flow

Best Answers

Solutions Coming Soon

Related Binary Search Problems

Festival Drone Altitude Limit

Lantern Stage Volume Check

Pier Ticket Window Time

Harbor Relay Coverage Radius

Marina Beacon Frequency Search

Minimal Climb Cost

Comments (0)

Join the Discussion