How do I minimize skips in the Minimum Skips to Arrive at Meeting On Time problem?

To minimize skips, use dynamic programming to track the minimum number of skips required to arrive on time, considering the travel time and possible skips for each road.

What dynamic programming approach is needed for this problem?

The approach involves maintaining a DP table that tracks the current state at each road, considering both the time and the number of skips needed.

What is the time complexity of the Minimum Skips to Arrive at Meeting On Time problem?

The time complexity depends on the final approach, typically O(n * k), where n is the number of roads and k is the maximum number of skips.

Can the solution be optimized for larger inputs?

Yes, the solution can be optimized by refining the DP approach and reducing unnecessary calculations during state transitions.

What if I cannot arrive on time even with all skips?

If it's impossible to arrive on time, the solution should return `-1` to indicate the infeasibility of the journey.

#1883

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

准时抵达会议现场的最小跳过休息次数

给你一个整数 hoursBefore ，表示你要前往会议所剩下的可用小时数。要想成功抵达会议现场，你必须途经 n 条道路。道路的长度用一个长度为 n 的整数数组 dist 表示，其中 dist[i] 表示第 i 条道路的长度（单位：千米）。另给你一个整数 speed ，表示你在道路上前进的速度（…

数组动态规划

题目描述

给你一个整数 hoursBefore ，表示你要前往会议所剩下的可用小时数。要想成功抵达会议现场，你必须途经 n 条道路。道路的长度用一个长度为 n 的整数数组 dist 表示，其中 dist[i] 表示第 i 条道路的长度（单位：千米）。另给你一个整数 speed ，表示你在道路上前进的速度（单位：千米每小时）。

当你通过第 i 条路之后，就必须休息并等待，直到 下一个整数小时 才能开始继续通过下一条道路。注意：你不需要在通过最后一条道路后休息，因为那时你已经抵达会议现场。

例如，如果你通过一条道路用去 1.4 小时，那你必须停下来等待，到 2 小时才可以继续通过下一条道路。如果通过一条道路恰好用去 2 小时，就无需等待，可以直接继续。

然而，为了能准时到达，你可以选择跳过一些路的休息时间，这意味着你不必等待下一个整数小时。注意，这意味着与不跳过任何休息时间相比，你可能在不同时刻到达接下来的道路。

例如，假设通过第 1 条道路用去 1.4 小时，且通过第 2 条道路用去 0.6 小时。跳过第 1 条道路的休息时间意味着你将会在恰好 2 小时完成通过第 2 条道路，且你能够立即开始通过第 3 条道路。

返回准时抵达会议现场所需要的 最小跳过次数 ，如果 无法准时参会 ，返回 -1 。

示例 1：

输入：dist = [1,3,2], speed = 4, hoursBefore = 2
输出：1
解释：
不跳过任何休息时间，你将用 (1/4 + 3/4) + (3/4 + 1/4) + (2/4) = 2.5 小时才能抵达会议现场。
可以跳过第 1 次休息时间，共用 ((1/4 + 0) + (3/4 + 0)) + (2/4) = 1.5 小时抵达会议现场。
注意，第 2 次休息时间缩短为 0 ，由于跳过第 1 次休息时间，你是在整数小时处完成通过第 2 条道路。

示例 2：

输入：dist = [7,3,5,5], speed = 2, hoursBefore = 10
输出：2
解释：
不跳过任何休息时间，你将用 (7/2 + 1/2) + (3/2 + 1/2) + (5/2 + 1/2) + (5/2) = 11.5 小时才能抵达会议现场。
可以跳过第 1 次和第 3 次休息时间，共用 ((7/2 + 0) + (3/2 + 0)) + ((5/2 + 0) + (5/2)) = 10 小时抵达会议现场。

示例 3：

输入：dist = [7,3,5,5], speed = 1, hoursBefore = 10
输出：-1
解释：即使跳过所有的休息时间，也无法准时参加会议。

提示：

n == dist.length
1 <= n <= 1000
1 <= dist[i] <= 10⁵
1 <= speed <= 10⁶
1 <= hoursBefore <= 10⁷

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i][j]$ 表示考虑前 $i$ 条道路，恰好跳过 $j$ 次休息时间的最短用时。初始时 $f[0][0]=0$ ，其余 $f[i][j]=\infty$ 。

由于我们可以选择跳过或者不跳过第 $i$ 条道路的休息时间，因此我们可以列出状态转移方程：

f[i][j]=\min\left\{\begin{aligned} \lceil f[i-1][j]+\frac{d_i}{s}\rceil & \textit{不跳过第 $i$ 条道路的休息时间} \\ f[i-1][j-1]+\frac{d_i}{s} & \textit{跳过第 $i$ 条道路的休息时间} \end{aligned}\right.

其中 $\lceil x\rceil$ 表示将 $x$ 向上取整。需要注意的是，由于我们需要保证恰好跳过 $j$ 次休息时间，因此我们必须有 $j\le i$ ；另外，如果 $j=0$ ，不能跳过任何休息时间。

由于浮点数运算以及向上取整运算可能会带来精度误差，因此我们引入一个常量 $eps = 10^{-8}$ 表示一个极小的正实数，在浮点数取整前先减去 $eps$ ，最后在比较 $f[n][j]$ 和 $hoursBefore$ 时，需要加上 $eps$ 。

时间复杂度 $O(n^2)$ ，空间复杂度 $O(n^2)$ 。其中 $n$ 是道路的数量。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:
        n = len(dist)
        f = [[inf] * (n + 1) for _ in range(n + 1)]
        f[0][0] = 0
        eps = 1e-8
        for i, x in enumerate(dist, 1):
            for j in range(i + 1):
                if j < i:
                    f[i][j] = min(f[i][j], ceil(f[i - 1][j] + x / speed - eps))
                if j:
                    f[i][j] = min(f[i][j], f[i - 1][j - 1] + x / speed)
        for j in range(n + 1):
            if f[n][j] <= hoursBefore + eps:
                return j
        return -1

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Is the candidate familiar with dynamic programming and state transitions?
question_mark
Can the candidate effectively handle edge cases and constraints, such as when it's impossible to arrive on time?
question_mark
Does the candidate consider both the travel time and the skips when formulating the solution?

warning

常见陷阱

外企场景

error
Forgetting to account for the last road not requiring a rest.
error
Misunderstanding the calculation of travel time for each road and the impact of skips.
error
Overcomplicating the DP solution or failing to optimize the state transitions.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem by introducing variable speeds for different roads.
arrow_right_alt
Change the constraint to allow skipping rests at specific times only.
arrow_right_alt
Add extra conditions such as required stops for rest at specific intervals.

help

常见问题

外企场景

继续练习

#1879 两个数组最小的异或值之和 #1872 石子游戏 VIII #1911 最大交替子序列和