Minimize Max Distance to Gas Station


  • 0

    Click here to see the full article post


  • 1
    J

    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.


  • 0

    @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).


  • 0
    T

    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)
    

  • 0

    @TheStrayCat What does your count[i] mean?


  • 0
    C

    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]
    

  • 0
    T

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


  • 0
    This post is deleted!

  • 1
    Q

    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


  • 0
    C

    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


  • 0
    D

    @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.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]


  • 0
    D

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


Log in to reply
 

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