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.