# 774. Minimize Max Distance to Gas Station

- You are given an array "stations" representing the positions of the gas stations on the x-axis.
- Let "penalty" be the maximum distance between adjacent gas stations.
- Return the minumum possible value of "penalty" after "adding k gas stations" anywhere on x-axis.

stations = [2, 5, 8] 
k = 2 for new stations

    2   3'  5   6'   9 
min   1   2   1   3   = 3 -> sol1
    2   3'  5   7'   9 
min.  1   2.  2.  2.  = 2 -> sol2 *

[2, 5, 9, 15] 
step 1 find all distance
[3, 4, 6]

k avaivle station
step 2 use k to divide largest distance
k=1 6 -> 3  [3:3, 4:1]
k=2 4 -> 2  [2:2, 3:3]

example
[2,      4,        6] k=3
[2,   2, 2,  2, 2, 2]

distance
[2, 4, 6]
     penalty
k=0    6      [2, 4, 6]  6 max -> 3 3
k=1    4      [2, 4, 3, 3] 4 max -> 2 2
k=2    3      [2, 2, 2, 3, 3] 2*3 -> 
k=3    2      [2, 2, 2, 2, 2, 2]
..
k=9    1

the penalty is decreasing when k increase
(1) given k -> find penalty is hard
(2) given penalty -> find how many gas station at least should add

assume p = 2
[2, 4, 6]  k = 3
2  4->[2, 2], 6 k = 2 
2, 2, 2, 6->[2, 4] k = 1
2, 2, 2, 2, 4->[2, 2] k = 0 -> okay p = 2 is okay

  V
0 1 2

    # stations = [0, 2, 6, 12] k =3
    # stations = [1] k =1  -> 0
    # stations = [1, 2] k =0  -> 0
    
    # sort floating point
    def findMiniumPenalty(stations, k):
        if len(stations) <= 1:
            return 0
        # get all distances
        distances = []
        # [2, 4, 6] = distances
        for i in range(1, len(stations)):
            distances.append(stations[i]-stations[i-1])
    
        
        # valid function for p
        # check is it possible to make minimal penalty in given new k stations 
        def valid(penalty):
            available = k
            # penalty = 2
            #[2, 4, 6] = distances
            for i in range(len(distances)):
                if distances[i] <= penalty:
                    #[2] skip
                    continue
                else:
                    #[4 ,6]
                    """tmp = distances[i] # 6
                    while tmp > penalty:
                        if available == 0: # 1 
                            return False
                        tmp -= penalty # tmp = 4
                        available -= 1 # available = 0"""
                    # even 6//3 -> 2 mod 0  [3, 3] 1
                    # odd 5//3 -> 1 mod 2   [3, 2] 1
                    # even 4//3 -> 1 mod 1  [3, 1] 1
                    
                    need, mod = divmod(distances[i], penalty)
                    if mod == 0:
                        need -= 1
                    if need > available:
                        return False
                    available -= need
            return True
        
        
        # binary serach for p
        loPenalty = 0
        hiPenalty = max(distances)
        ans = hiPenalty
        while lo <= hi:
            midPenalty = (loPenalty + hiPenalty)//2
            if valid(midPenalty):
                ans = midPenalty
                hiPenalty = midPenalty - 1
            else:
                loPenalty = midPenalty + 1
        return ans