Welcome to Subscribe On Youtube

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;
        }
    }
    
  • // OJ: https://leetcode.com/problems/minimize-max-distance-to-gas-station/
    // Time: O(N * (logN + logM))
    // Space: O(1)
    class Solution {
        bool valid(vector<int> &A, double M, int k) {
            for (int i = 1; i < A.size(); ++i) {
                k -= (int)((A[i] - A[i - 1]) / M);
                if (k < 0) return false;
            }
            return true;
        }
    public:
        double minmaxGasDist(vector<int>& A, int k) {
            double L = 0, R = 1e8, eps = 1e-6;
            while (R - L >= eps) {
                double M = (L + R) / 2;
                if (valid(A, M, k)) R = M;
                else L = M;
            }
            return L;
        }
    };
    
  • class Solution:
        def minmaxGasDist(self, stations: List[int], k: int) -> float:
            def check(x):
                return sum(int((b - a) / x) for a, b in pairwise(stations)) <= k
    
            left, right = 0, 1e8
            while right - left > 1e-6:
                mid = (left + right) / 2
                if check(mid):
                    right = mid
                else:
                    left = mid
            return left
    
    
    
  • func minmaxGasDist(stations []int, k int) float64 {
    	check := func(x float64) bool {
    		s := 0
    		for i, v := range stations[:len(stations)-1] {
    			s += int(float64(stations[i+1]-v) / x)
    		}
    		return s <= k
    	}
    	var left, right float64 = 0, 1e8
    	for right-left > 1e-6 {
    		mid := (left + right) / 2.0
    		if check(mid) {
    			right = mid
    		} else {
    			left = mid
    		}
    	}
    	return left
    }
    

All Problems

All Solutions