[Google] Minimize Max Distance to Gas Station

Problem: 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.5
Explanation: All possible concatenations are "","un","iq","ue","uniq" and "ique".
Maximum length is 4.

Constraints:

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

Approach: We are going to use binary search here. How? What is our sorted array here, it is given as input that is our stations distance array. What is initial left? left is the lowest distance possible which is 0. Now  what is initial right; The right will be the maximum distance possible in the given array which is last station distance - first station distance. 

Now we will take the mid of left and right distance and see how many stations can be placed if we use mid distance. If number of station can be placed is <= k then we know that we can make the distance less so we will make right = mid and otherwise if the stations placed are more than k then we have to make distance more i.e. we need to make left = mid.

In the end we can return left or right.

 

Implementation in Java:

    public double minmaxGasDist(int[] stations, int k) {

        int length = stations.length;

        double left = 0;

        double right = stations[length - 1] - stations[0];

        while (right - left > 1e-6) {

            double mid = left + (right - left) / 2;

            if (isFeasible(stations, k, mid)) {

                right = mid;

            }

            else {

                left = mid;

            }

        }

        return right;

    }

    private boolean isFeasible(int[] stations, int k, double dist) {

        int count = 0;

        for (int i = 1; i < stations.length; ++i) {

            count += (int)((stations[i] - stations[i - 1]) / dist);

        }

        return count <= k;

    }

Complexity: O(nlogD) where D is the difference between station[n-1] and stations[0].