774

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;
    }
};