## 774. 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.

## Rust Solution

struct Solution;

impl Solution {
fn minmax_gas_dist(mut stations: Vec<i32>, k: i32) -> f64 {
stations.sort_unstable();
let stations: Vec<f64> = stations.into_iter().map(|x| x as f64).collect();
let mut lo = 0.0;
let mut hi = 1e8;
while (hi - lo) > 1e-6 {
let mi = (hi + lo) / 2.0;
if Self::possible(mi, &stations, k) {
hi = mi;
} else {
lo = mi;
}
}
lo
}

fn possible(dist: f64, stations: &[f64], k: i32) -> bool {
let mut count = 0;
for i in 1..stations.len() {
count += ((stations[i] - stations[i - 1]) / dist) as i32;
}
count <= k
}
}

#[test]
fn test() {
use assert_approx_eq::assert_approx_eq;
let stations = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
let k = 9;
let res = 0.5;
assert_approx_eq!(Solution::minmax_gas_dist(stations, k), res);
}

Having problems with this solution? Click here to submit an issue on github.