23.07.26 Today’s Leetcode

1870. Minimum Speed to Arrive on Time (medium)

Binary Search

class Solution:
    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:

        n = len(dist)
        v = sum(dist)
        if hour <= n - 1:
            return -1
        if v <= hour:
            return 1

        def get_time(speed):
            time = 0
            for i, d in enumerate(dist):
                time += d / speed
                if i < n - 1 and time - math.floor(time) > 0:
                    time = math.ceil(time)
            
            return time

        i = 1
        p = hour - n + 1
        j = 1 + max(int(dist[-1] / p), max(dist))

        while i < j:
            mid = (i + j) // 2
            if get_time(mid) <= hour:
                j = mid
            else:
                i = mid + 1
        
        return i