Minimize Max Distance to Gas Station

• Excellent explanations.
In approach 4#, maybe the line
sum(int((stations[I+1] - stations[I]) / D) ... )
should be something like
sum(int((stations[I+1] - stations[I]) / D - 1).ceil ...) ?
We need only X/D - 1 stations to ensure every subinterval has size no more than D if X/D happens to be an integer.

• @awice You forgot to sort the stations. Nothing in the problem says they're sorted, and at least your approach #4 needs that (I didn't try the others).

• Hi all,

I would like to show my solution which gives the exact answer and runs faster than binary search (244 ms < 1030 ms).

We have `num` intervals (`num = len(stations)-1`) with lengths stored in the `delta` list. Our goal is to subdivide them into `K+nums` subintervals by adding `K` additional breakpoints so as to make the longest subinterval as short as possible.

Intuitively, this would be true if all subintervals had approximately equal lengths, that is, `delta[i]/count[i]` were about the same for all `i`. We know that the sum of all elements in `delta` is the difference between the last and the first elements in `stations`, call it `n` (here I cheated a little bit by making an assumption that `stations` was sorted in all test cases, and by pure chance I was correct). Hence, `count[i]` should be not too far away from `1 + delta[i]*K/n`, which is the hypothetical number of parts in case breakpoints are allocated proportionally based on the distance.

But unfortunately, `delta[i]*K/n` is not always an integer. However, it is reasonable to assume that at least `count[i]>=1+int(delta[i]*K/n)`.

Now we allocate `1+int(delta[i]*K/n)` breakpoints to each interval, compute the remaining number of points (which never exceeds `num`) and finish the job by applying a priority queue as in approach #3. Here's the complete Python code:

``````from heapq import heappop, heappush

class Solution:
def minmaxGasDist(self, stations, K):
num = len(stations)-1
delta = [stations[i+1]-stations[i] for i in range(num)]
n = stations[-1]-stations[0]
count = [1+int(r*K/n) for r in delta]
steps = K+num-sum(count)

Q = []
for i in range (num):
heappush(Q, (-delta[i]/count[i], count[i]))

for i in range(steps):
max_dist = heappop(Q)
new_dist, new_count = max_dist[1]*max_dist[0]/(max_dist[1]+1), max_dist[1]+1
heappush(Q,(new_dist,new_count))

ints = [-heappop(Q)[0] for i in range(len(Q))]

return max(ints)
``````

• @TheStrayCat What does your `count[i]` mean?

• Simple 10-line Python O(n log(n)) priority queue solution.
We know that the minmax distance is no more than (station(n)-station(1)) / K, so let's start from there:

``````    def minmaxGasDist(self, stations, K):
d = (stations[len(stations)-1] - stations[0]) / float(K)
heap = []
for i in range(len(stations)-1):
n = max(1, int((stations[i+1]-stations[i]) / d))
K -= (n-1)
heapq.heappush(heap, (float(stations[i]-stations[i+1]) / n, stations[i], stations[i+1], n))

for i in range(K):
(d, a, b, n) = heap[0]
heapq.heapreplace(heap, ((a-b)/(n+1.0), a, b, n+1))
return -heap[0][0]
``````

• @ManuelP The number of pieces into which the i-th interval is divided.

• This post is deleted!

• Actually we know if K>0, there will be a minmax distance exist and this minmax<max gap for this question. So for the binary search optimized solution is that we can sort the gap and set the high variable to the gap[gap.length-1] to speed up algorithm. Java code like below.

class Solution {
public double minmaxGasDist(int[] stations, int K) {
int[] gap = new int[stations.length-1];
for(int i=0;i<stations.length-1;i++){
gap[i]= stations[i+1] - stations[i];
}
Arrays.sort(gap);
double low= 0, high=gap[gap.length-1];

``````    while(high-low >1e-6){
double mid = (double)(low+high)/2.0;
if(possible(mid,gap,K)){
high=mid;
}else{
low=mid;
}
}
return low;
}

public boolean possible(double step, int[] gap, int K){
int need_to_use =0;
for(int i=0;i<gap.length;i++){
need_to_use += (int)(gap[i]/step);
}
return need_to_use <= K;
}
``````

}

The time complexity will be O(N logW), W should be the W = max_gap*10^6
The space complexity will be O(N), to store the gap

• Regarding the priority queue, this solution does not meet TLE. Please update if possible. Thanks. https://discuss.leetcode.com/topic/118812/simple-10-line-python-o-n-log-n-priority-queue-solution

• Actually we know if K>0, there will be a minmax distance exist and this minmax<max gap for this question. So for the binary search optimized solution is that we can sort the gap and set the high variable to the gap[gap.length-1] to speed up algorithm. Java code like below.

Great solution.
I think W should be min(max_gap * K, 10^8) as stations will be in range [0, 10^8]

• @cja
great solution, but I think the complexity is O(max(n,K) * log(n))

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.