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?