Minimum Speed to Arrive on Time LeetCode solution in Python

1
# Runtime: 5298 ms (Top 60.74%) | Memory: 27.4 MB (Top 98.14%)
2

3

4
class Solution:
5
    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:
6
        # the speed upper is either the longest train ride: max(dist),
7
        # or the last train ride divide by 0.01: ceil(dist[-1] / 0.01).
8
        # notice: "hour will have at most two digits after the decimal point"
9
        upper = max(max(dist), ceil(dist[-1] / 0.01))
10
        #
11
        # the function to calcute total time consumed
12
        total = lambda speed: sum(map(lambda x: ceil(x / speed), dist[:-1])) + (
13
            dist[-1] / speed
14
        )
15
        # the case of impossible to arrive office on time
16
        if total(upper) > hour:
17
            return -1
18
        #
19
        # binary search: find the mimimal among "all" feasible answers
20
        left, right = 1, upper
21
        while left < right:
22
            mid = left + (right - left) // 2
23
            if total(mid) > hour:
24
                left = mid + 1  # should be larger
25
            else:
26
                right = mid  # should explore a smaller one
27
        return right