Minimum Skips to Arrive at Meeting On Time LeetCode solution in Python

1
class Solution:
2
    def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:
3
        if sum(dist) / speed > hoursBefore:
4
            return -1  # impossible
5

6
        @cache
7
        def fn(i, k):
8
            """Return min time (in distance) of traveling first i roads with k skips."""
9
            if k < 0:
10
                return inf  # impossible
11
            if i == 0:
12
                return 0
13
            return min(
14
                ceil((fn(i - 1, k) + dist[i - 1]) / speed) * speed,
15
                dist[i - 1] + fn(i - 1, k - 1),
16
            )
17

18
        for k in range(len(dist)):
19
            if fn(len(dist) - 1, k) + dist[-1] <= hoursBefore * speed:
20
                return k