LeetCode [774] Minimize Max Distance to Gas Station

 774. Minimize Max Distance to Gas Station

Hard

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

class Solution { double E = 1e-6; int compare(double a, double b) { if(Math.abs(a-b)<=E) return 0; else if(a>b) return 1; else return -1; } public double minmaxGasDist(int[] stations, int K) { double l = E, r = 2000; while(compare(l, r)<=0) { double mid = l + (r-l)/2.0; // System.out.println(l + " " + r + " " + mid); if(valid(stations, K, mid)) { if(compare(mid, 0)==0 || !valid(stations, K, mid-E)) return mid; r = mid-E; }else{ l = mid+E; } } return l; } boolean valid (int[] stations, int K, double target) { int n = stations.length; int added = 0; for(int i=1; i<n; ++i){ double distance = (double)stations[i]-(double)stations[i-1]; if(distance > target){ added += (int)Math.floor(distance/target); } if(added>K) return false; } return true; } }