准时抵达会议现场的最小跳过休息次数
难度:
标签:
题目描述
代码结果
运行时间: 1066 ms, 内存: 16.2 MB
/*
* Problem: Similar to the Java solution, but using Java Streams where applicable.
* Idea: Utilize streams for operations like array initialization and minimum calculation.
*/
import java.util.Arrays;
import java.util.stream.IntStream;
public class MeetingSchedulerStream {
public int minSkips(int[] dist, int speed, int hoursBefore) {
int n = dist.length;
double[][] time = new double[n + 1][n + 1];
Arrays.stream(time).forEach(row -> Arrays.fill(row, Double.MAX_VALUE));
time[0][0] = 0;
for (int i = 1; i <= n; i++) {
double t = (double) dist[i - 1] / speed;
for (int j = 0; j <= i; j++) {
if (j < i) {
time[i][j] = Math.min(time[i][j], Math.ceil(time[i - 1][j]) + t);
}
if (j > 0) {
time[i][j] = Math.min(time[i][j], time[i - 1][j - 1] + t);
}
}
}
return IntStream.range(0, n + 1)
.filter(j -> time[n][j] <= hoursBefore)
.findFirst()
.orElse(-1);
}
}
解释
方法:
此题考虑使用动态规划解决。定义dp[j]表示在跳过前j次休息的条件下,经过当前所有道路所需的最少时间(调整至下一个整点开始)。在迭代每一条道路的过程中,我们需要更新dp数组,以包括两种情况:(1) 跳过这条道路的休息时间,即直接加上这条道路的行驶时间;(2) 不跳过这条道路的休息时间,即将当前总时间调整到下一个整点小时,再加上这条道路的行驶时间。我们为每一种情况都计算可能的时间,并更新dp数组。最后,检查dp数组中最小的j值,使得dp[j]不超过hoursBefore * speed,即可到达会议现场的时间限制。如果所有j都无法满足条件,则返回-1。
时间复杂度:
O(n^2)
空间复杂度:
O(n)
代码细节讲解
🦆
动态规划的状态转移方程是怎么定义的,为什么要使用两种情况(跳过和不跳过休息)来更新dp数组?
▷🦆
在不跳过休息的情况下,为什么更新dp[j]的值时使用((dp[j] + dist[i] - 1) // speed + 1) * speed这个表达式?这个表达式的意义是什么?
▷🦆
题解中提到,最后需要检查dp数组中最小的j值使得dp[j]不超过hoursBefore * speed,这里的逻辑是否能保证在所有的跳过休息的情况下找到最优解?
▷