Skip to content

774. Minimize Max Distance to Gas Station 👍

  • Time: $O(n\log \frac{\max - \min}{10^{-6}})$
  • Space: $O(1)$
 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
class Solution {
 public:
  double minmaxGasDist(vector<int>& stations, int k) {
    constexpr double kErr = 1e-6;
    double l = 0;
    double r = stations.back() - stations[0];

    while (r - l > kErr) {
      const double m = (l + r) / 2;
      if (check(stations, k, m))
        r = m;
      else
        l = m;
    }

    return l;
  }

 private:
  // Returns true if can use <= k gas stations to ensure that each adjacent
  // distance between gas stations <= m.
  bool check(const vector<int>& stations, int k, double m) {
    for (int i = 1; i < stations.size(); ++i) {
      const int diff = stations[i] - stations[i - 1];
      if (diff > m) {
        k -= ceil(diff / m) - 1;
        if (k < 0)
          return false;
      }
    }
    return true;
  };
};

 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
class Solution {
  public double minmaxGasDist(int[] stations, int k) {
    final double kErr = 1e-6;
    double l = 0;
    double r = stations[stations.length - 1] - stations[0];

    while (r - l > kErr) {
      final double m = (l + r) / 2;
      if (check(stations, k, m))
        r = m;
      else
        l = m;
    }

    return l;
  }

  // Returns true if can use <= k gas stations to ensure that each adjacent
  // distance between gas stations <= m.
  private boolean check(int[] stations, int k, double m) {
    for (int i = 1; i < stations.length; ++i) {
      final int diff = stations[i] - stations[i - 1];
      if (diff > m) {
        k -= Math.ceil(diff / m) - 1;
        if (k < 0)
          return false;
      }
    }
    return true;
  };
}

 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
class Solution:
  def minmaxGasDist(self, stations: list[int], k: int) -> float:
    kErr = 1e-6
    l = 0
    r = stations[-1] - stations[0]

    def possible(k: int, m: float) -> bool:
      """
      Returns True if can use <= k gas stations to ensure that each adjacent
      distance between gas stations <= m.
      """
      for a, b in zip(stations, stations[1:]):
        diff = b - a
        if diff > m:
          k -= math.ceil(diff / m) - 1
          if k < 0:
            return False
      return True

    while r - l > kErr:
      m = (l + r) / 2
      if possible(k, m):
        r = m
      else:
        l = m

    return l