# 774.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:
stations.length will be an integer in range [10, 2000].
stations[i] will be an integer in range [0, 10^8].
K will be an integer in range [1, 10^6].
Answers within 10^-6 of the true value will be accepted as correct.``````

## ไปฃ็ 

### Approach #1 Dynamic Programming [Memory Lmit Exceeded]

Time: O(NK^2) && Space: O(NK)

``````class Solution {
public double minmaxGasDist(int[] stations, int K) {
int N = stations.length;
double[] deltas = new double[N-1];
for (int i = 0; i < N-1; i++) {
deltas[i] = stations[i+1] - stations[i];
}
double[][] dp = new double[N-1][K+1];
for (int i = 0; i <= K; i++)
dp[0][i] = deltas[0] / (i+1);

for (int p = 1; p < N-1; p++) {
for (int k = 0; k <= K; k++) {
double bns = 999999999;
for (int x = 0; x <= k; x++) {
bns = Math.min(bns, Math.max(deltas[p] / (x+1), dp[p-1][k-x]));
}
dp[p][k] = bns;
}
}

return dp[N-2][K];
}
}``````
``````class Solution {
public double minmaxGasDist(int[] stations, int K) {
int count;
int N = stations.length;
double left = 0;
double right = stations[N-1] - stations[0];
while (right - left > 1e-6) { //  left - right < 1e-6 TLE
double mid = (left + right) / 2;
count = 0;
for (int i = 0; i < N-1; i++) {
count += (int)((stations[i+1] - stations[i]) / mid);
}
if (count > K) {
left = mid;
} else {
right = mid;
}
}
return right;
}
}``````

### Approach #3 PriorityQueue Greedy [Time Limit Exceeded]

``````public double minmaxGasDist(int[] stations, int K) {
PriorityQueue<double[]> pq = new PriorityQueue<double[]>(
(a,b) -> (a[0]/a[1] < b[0]/b[1]) ? 1 : -1);
for (int i = 1; i < stations.length; ++i) {
pq.add(new double[] {stations[i] - stations[i-1], 1.0});
}
while (K-- > 0) {
double [] cur = pq.poll();
++cur[1];