We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimize Max Distance to Gas Station

Number: 788

Difficulty: Hard

Paid? Yes

Companies: Google

Problem Description

Given an array of gas station positions along the x-axis and an integer k, add k new gas stations (which can be placed anywhere, not necessarily at integer positions) such that the maximum distance between any two adjacent stations is minimized. The answer must be accurate within 10^-6.

Key Insights

  • The optimal "penalty" (i.e., the maximum distance between adjacent stations after placement) can be found using binary search over a continuous distance range.
  • For each candidate distance (mid), simulate the number of gas stations required by iterating over each adjacent station gap and calculating:
    • stations_required = ceil(gap / mid) - 1
  • If the total number of required additional stations is less than or equal to k, then mid is a feasible candidate; otherwise, it is too small.
  • Continue the binary search until the gap between low and high is within the desired tolerance (1e-6).

Space and Time Complexity

Time Complexity: O(n * log(max_gap/precision)), where n is the number of stations. Space Complexity: O(1) (ignoring input storage)

Solution

We use binary search over the possible maximum distances. The algorithm sets low = 0 and high = the maximum gap between adjacent stations. For a candidate distance mid, we count how many new stations are required for all gaps by computing ceil(gap / mid) - 1. If the total required is within k, we try a smaller candidate; otherwise, we increase the candidate distance. This approach efficiently zooms into the minimum possible maximum distance (penalty).

Code Solutions

import math

def minmaxGasDist(stations, k):
    # Initialize the search range between 0 and the maximum gap between existing stations
    low = 0.0
    high = max(stations[i+1] - stations[i] for i in range(len(stations)-1))
    
    # Use binary search with a tolerance of 1e-6
    while high - low > 1e-6:
        mid = (low + high) / 2.0
        used = 0
        # Calculate additional stations needed for each gap
        for i in range(1, len(stations)):
            gap = stations[i] - stations[i-1]
            used += math.ceil(gap / mid) - 1
        # If the used stations are less than or equal to k, try a smaller distance
        if used <= k:
            high = mid
        else:
            low = mid
    return high

# Example usage:
if __name__ == '__main__':
    print("{:.5f}".format(minmaxGasDist([1,2,3,4,5,6,7,8,9,10], 9)))
    print("{:.5f}".format(minmaxGasDist([23,24,36,39,46,56,57,65,84,98], 1)))
← Back to All Questions