774. Minimize Max Distance to Gas Station

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

(1) Java

class Solution {
    public double minmaxGasDist(int[] stations, int K) {
        if (stations.length <= 1) {
            return 0.0;
        }
        int num = stations.length;
        double[] intervals = new double[num-1];
        for (int i = 0; i < num-1; i++) {
            intervals[i] = stations[i+1]-stations[i];
        }
        double[][] dp = new double[num-1][K+1];
        for (int i = 0; i <= K; i++) {
            dp[0][i] = intervals[0]/(i+1.0);
        }
        for (int i = 1; i < num-1; i++) {
            for (int j = 0; j <= K; j++) {
                double tmp = 2000;
                for (int k = 0; k <= j; k++) {
                    tmp = Math.min(tmp, Math.max(intervals[i]/(k+1.0), dp[i-1][j-k]));
                }
                dp[i][j] = tmp;
            }
        }
        return dp[num-2][K];
    }
}

(2) Python

class Solution:
    def minmaxGasDist(self, stations, K):
        """
        :type stations: List[int]
        :type K: int
        :rtype: float
        """
        def getNeededStations(mi):
            num = 0
            for dist in dists:
                num += int(dist/mi)
            return num

        dists = [stations[i]-stations[i-1] for i in range(1, len(stations))]
        totalDist = sum(dists)
        lo, hi = 0, totalDist
        e = 0.0000001
        while hi-lo > e:
            mi = lo+(hi-lo)/2.0
            sd = getNeededStations(mi)
            if sd > K:
                lo = mi
            elif sd < K:
                hi = mi
            else:
                return mi
        return lo

(3) Scala