Formatted question description: https://leetcode.ca/all/774.html

774. Minimize Max Distance to Gas Station

Level

Hard

Description

On a horizontal number line, we have gas stations at positions stations[0], stations[1], ..., stations[N-1], where N = stations.length.

Now, we add K more gas stations so that D, the maximum distance between adjacent gas stations, is minimized.

Return the smallest possible value of D.

Example:

Input: stations = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], K = 9

Output: 0.500000

Note:

  1. stations.length will be an integer in range [10, 2000].
  2. stations[i] will be an integer in range [0, 10^8].
  3. K will be an integer in range [1, 10^6].
  4. Answers within 10^-6 of the true value will be accepted as correct.

Solution

Use binary search. Sort stations and initialize low to 0 and high to the difference between the maximum element in stations and the minimum element in stations. While high - low > 1e-6, do binary search. Each time set mid to be the average of low and high and use mid as a candidate of D to calculate the minimum number of gas stations to be added. If the minimum number of gas stations to be added is less than or equal to K, then set high = mid. Otherwise, set low = mid. Finally, return low.

class Solution {
    public double minmaxGasDist(int[] stations, int K) {
        Arrays.sort(stations);
        int length = stations.length;
        double low = 0, high = stations[length - 1] - stations[0];
        while (high - low > 1e-6) {
            double mid = (low + high) / 2;
            int minStations = 0;
            for (int i = 1; i < length; i++)
                minStations += (int) ((stations[i] - stations[i - 1]) / mid);
            if (minStations <= K)
                high = mid;
            else
                low = mid;
        }
        return low;
    }
}

All Problems

All Solutions