LeetCode Solutions
774. Minimize Max Distance to Gas Station
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:
// True if can use k or less gas stations to ensure
// Each adjacent distance between gas stations is at most 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;
};
};
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;
}
// True if can use k or less gas stations to ensure
// Each adjacent distance between gas stations is at most 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;
};
}
class Solution:
def minmaxGasDist(self, stations: List[int], k: int) -> float:
kErr = 1e-6
l = 0
r = stations[-1] - stations[0]
# True if can use k or less gas stations to ensure
# Each adjacent distance between gas stations is at most m
def possible(k: int, m: float) -> bool:
for a, b in zip(stations, stations[1:]):
diff = b - a
if diff > m:
k -= 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