774. Minimize Max Distance to Gas Station

-
https://www.lintcode.com/problem/minimize-max-distance-to-gas-station/
https://leetcode.com/problems/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.
---
Related problems
---
Intuition
Corner cases =>
    Worst case => Input 1 station at 0, K = 1 => Place new station furthest away at 10 ^ 8 => hi = 1e8
    Best case => Input 2 stations at 0, 2 * 1e -6 => Place new station at mid ~ 1e -6 => lo = 1e-6

Any placement which reduces distance below 1e -6 is invalid

Perform binary search between lo and hi

  • Terminate loop till search space is in bounds = > hi - lo >= 1e-6
  • Save result if valid, and continue searching in left half
  • Use hi = mid, lo = mid during sample walkthrough. 
  • Code works with hi = mid - 1e-6, lo = mid + 1e-6
  • isValid function
    • TODO
---
Time - O(N Log (Search Space) ) => O( N Log 1e 8 / 1e -6)) => O(N Log 1e14) => O(N) 
Space - O(1)
---
public class Solution {
/**
* @param stations: an integer array
* @param k: an integer
* @return: the smallest possible value of D
*/
double PRECISION = 1e-6;
public double minmaxGasDist(int[] stations, int k) {
double lo = 0, hi = 1e8;
double ans = lo;
while (hi - lo >= PRECISION) {
double mid = (hi + lo) / 2;
if (isValid(mid, stations, k)) {
ans = mid;
// Can use hi = mid in walkthrough, code works too
hi = mid - PRECISION;
} else {
// Can use lo = mid in walkthrough, code works too
lo = mid + PRECISION;
}
}
return ans;
}
// Count number of gas stations needed to make k valid
private boolean isValid(double mid, int[] stations, int k) {
int numOfValidGaps = 0;
for (int i = 0; i < stations.length - 1; i++) {
numOfValidGaps += (int) (stations[i + 1] - stations[i]) / mid;
}
return numOfValidGaps <= k;
}
}
view raw 774.MinimizeMaxDistanceToGasStationBinarySearch.java hosted with ❤ by GitHub