512会议按时抵达所需的最小延迟跳过次数

解题思路

1. 思路
   使用动态规划求解。在每条路线上维护一个数组 dp，其中 dp[i][j] 表示前i条路线后恰好跳过 j 次等待时所需的最短时间。然后可以使用滚动数组进行优化，即只维护一个长度为 n 的 dp 数组。

2. 状态转移

   • 对于第一条路线，时间为 dist[0] / speed，不需要等待。
   • 对于后续路线，第 i 条的时间有两种选择：
     • 不跳过等待：需要等待至最近的整数小时，即 dp[j] = ceil(前一状态的时间) + 当前路程时间
     • 跳过等待：直接加上当前路程的时间，即 dp[j] = 前一状态的时间 + 当前路程时间，同时跳过次数增加 1
       最后取两种方法的较优值更新 dp。

实现代码

from typing import List
from math import ceil
inf = float("inf")
def solution(dist: List[int], speed: int, hoursBefore: int) -> int:
    n = len(dist)
    pre = [inf] * n
    pre[0] = dist[0] / speed
    for i in range(1, n):
        cur = [inf] * n
        for j in range(i + 1):
            # 用, 不用
            cur[j] = min(pre[j - 1], ceil(pre[j]) if pre[j] != inf else inf) + dist[i] / speed
        pre = cur.copy()
    for j in range(n):
        if pre[j] <= hoursBefore:
            return j
    return -1


if __name__ == '__main__':
    print(solution(dist=[2, 4, 3], speed=5, hoursBefore=3) == 0)
    print(solution(dist=[6, 2, 5], speed=7, hoursBefore=4) == 0)
    print(solution(dist=[8, 4, 6, 2], speed=4, hoursBefore=8) == 0)

复杂度分析

时间复杂度：$O(n^2)$，其中 n 为路线数量。
空间复杂度：$O(n)$。