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 thedelta
list. Our goal is to subdivide them intoK+nums
subintervals by addingK
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 alli
. We know that the sum of all elements indelta
is the difference between the last and the first elements instations
, call itn
(here I cheated a little bit by making an assumption thatstations
was sorted in all test cases, and by pure chance I was correct). Hence,count[i]
should be not too far away from1 + 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 leastcount[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 exceedsnum
) 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+numsum(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)


Simple 10line 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 = (n1) 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, ((ab)/(n+1.0), a, b, n+1)) return heap[0][0]


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.length1] to speed up algorithm. Java code like below.
class Solution {
public double minmaxGasDist(int[] stations, int K) {
int[] gap = new int[stations.length1];
for(int i=0;i<stations.length1;i++){
gap[i]= stations[i+1]  stations[i];
}
Arrays.sort(gap);
double low= 0, high=gap[gap.length1];while(highlow >1e6){ 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/simple10linepythononlognpriorityqueuesolution

@qinzhiguo said in Minimize Max Distance to Gas Station:
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.length1] 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]
