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

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

难度:

标签:

题目描述

代码结果

运行时间: 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] 为跳过前 j 次休息后,经过当前所有道路所需的最少时间。更新 dp 数组时,考虑两种情况:1) 跳过这条道路的休息时间,直接加上这条道路的行驶时间;2) 不跳过这条道路的休息时间,将当前总时间调整到下一个整点小时后,再加上这条道路的行驶时间。这两种情况确保我们能够根据不同的时间管理策略(即是否跳过休息),找到到达会议现场的最佳路径。
🦆
在不跳过休息的情况下,为什么更新dp[j]的值时使用((dp[j] + dist[i] - 1) // speed + 1) * speed这个表达式?这个表达式的意义是什么?
这个表达式用于将当前总时间调整到下一个整点小时。具体来说,`(dp[j] + dist[i] - 1)` 为通过当前道路后的总时间(减1是为了处理整除的边界条件)。整除 `speed` 后加1,将时间向上舍入到下一个整数,这代表需要等待到下一个整点小时开始。最后,乘以 `speed` 将单位从小时转换回距离单位。这样确保了在不跳过休息的情况下,每次行驶结束都能在整点时刻出发,这是休息策略的模拟。
🦆
题解中提到,最后需要检查dp数组中最小的j值使得dp[j]不超过hoursBefore * speed,这里的逻辑是否能保证在所有的跳过休息的情况下找到最优解?
是的,这个逻辑能保证在所有的跳过休息的情况下找到最优解。dp 数组记录了从0次到最多可能的跳过次数的每种情况下的最小时间。通过检查每个 dp[j] 是否小于等于 `hoursBefore * speed`,可以确保我们找到的解是在允许的时间内到达目的地的最少跳过次数。如果所有的 dp[j] 都超过了限制,返回 -1 表示无法在规定时间内到达。

相关问题