L774. Minimize Max Distance to Gas Station

Add k more stations, so that the maxD is minimized 

class Solution(object):
    def minmaxGasDist(self, stations, K):
        """
        :type stations: List[int]
        :type K: int
        :rtype: float
        """
        st = stations
        left, right = 1e-6, st[-1] - st[0]

        while left + 1e-6 < right:
            mid = (left + right) / 2
            count = 0
            for a, b in zip(st, st[1:]):  # eg,[1,2,3] print a,b = (1,2),(2,3)
                count += math.ceil((b - a) / mid) - 1  
            if count > K:
                left = mid #we need larger Max distance
            else:
                right = mid

        return right

#
what does mid mean? The variable mid here is actually a guess of the result, for example, we guess the Max Distance is 1.3.
with this guess, how many gas stations we need? There are several situations,
For example, mid = 1.3, arr = [1,2,4,8]
how many gas stations between 1 and 2? 0,
how many gas stations we need between 2 and 4? math.ceil((b - a) / mid) - 1 = ceil((4-2)/1.3) - 1 = 1
how many gas stations we need between 4 and 8? ceil((8-4)/1.3) - 1 = 3

what should we do if we don't have enough K?
Increase our guess, so we will need less extra gas stations. For example, if we guess the Max Distance is 2.1, we only need K = 1

Last updated

Was this helpful?