Heap

774. Minimize Max Distance to Gas Station

给一个一位数组，每个值代表一个gas station的位置，如果要增加K个gas station，求使得每个gas station之间距离的最大值最小？

• 解法1 Binary Search

  # Time : O(nlogm) m is st[-1]-st[0]
  class Solution(object):
    def minmaxGasDist(self, stations, K):
        start, end = 1e-6, stations[-1]-stations[0]
        while start + 1e-6 < end:
            mid = start + (end - start) / 2
            # count表示使每个gas station之间距离为mid的时候需要gas station的个数
            cnt = 0
            for a, b in zip(stations, stations[1:]):
                cnt += math.ceil((b - a) / mid) - 1 
            if cnt > K:
                start = mid
            else:
                end = mid
        return end
  

• 解法2 Heap

  # Time : O(nlogn)
  class Solution(object):
    def minmaxGasDist(self, stations, K):
        st = stations
        # minmax distance 从d开始
        d = (st[-1] - st[0]) / float(K)
        heap = []
        for v1, v2 in zip(st, st[1:]):
            # 求相邻gas station需要插入几个能满足d
            n = int((v2 - v1) / d)
            K -= n
            # MaxHeap v1, v2 两个Gas Station之间的minmax distance
            heapq.heappush(heap, [(v1-v2)/(n+1.0), v1, v2, n])
  
        for _ in xrange(K):
            d, v1, v2, n = heap[0]
            # 每次加入一个Gas Station到保持max distance的位置
            heapq.heapreplace(heap, [(v1-v2)/(n+2.0), v1, v2, n+1])
        return -heap[0][0]