774. Minimize Max Distance to Gas Station

774. Minimize Max Distance to Gas Station (Hard)

You are given an integer array stations that represents the positions of the gas stations on the x-axis. You are also given an integer k.

You should add k new gas stations. You can add the stations anywhere on the x-axis, and not necessarily on an integer position.

Let penalty() be the maximum distance between adjacent gas stations after adding the k new stations.

Return the smallest possible value of penalty(). Answers within 10-6 of the actual answer will be accepted.

 

Example 1:

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

Example 2:

Input: stations = [23,24,36,39,46,56,57,65,84,98], k = 1
Output: 14.00000

 

Constraints:

• 10 <= stations.length <= 2000
• 0 <= stations[i] <= 108
• stations is sorted in a strictly increasing order.
• 1 <= k <= 106

Companies:
Google

Related Topics:
Array, Binary Search

Similar Questions:

• Koko Eating Bananas (Medium)

Solution 1. Binary Answer

// OJ: https://leetcode.com/problems/minimize-max-distance-to-gas-station/
// Author: github.com/lzl124631x
// Time: O(N * (logN + logM)) where `M` is the maximum difference between two adjacent elements.
// Space: O(N)
class Solution {
    bool valid(vector<double> &dist, double M, int k) {
        for (int i = 0; i < dist.size() && dist[i] > M; ++i) {
            k -= ceil(dist[i] / M) - 1; // k -= int(dist[i] / M); also works
            if (k < 0) return false;
        }
        return true;
    }
public:
    double minmaxGasDist(vector<int>& A, int k) {
        vector<double> dist;
        for (int i = 1; i < A.size(); ++i) {
            dist.push_back(A[i] - A[i - 1]);
        }
        sort(begin(dist), end(dist), greater());
        double L = 0, R = dist[0], eps = 1e-6;
        while (R - L >= eps) {
            double M = (L + R) / 2;
            if (valid(dist, M, k)) R = M;
            else L = M;
        }
        return L;
    }
};

Or we can just use the original array.

// OJ: https://leetcode.com/problems/minimize-max-distance-to-gas-station/
// Author: github.com/lzl124631x
// 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;
    }
};