2224-转化时间需要的最少操作数

给你两个字符串 current 和 correct ，表示两个 24 小时制时间 。

24 小时制时间 按 "HH:MM" 进行格式化，其中 HH 在 00 和 23 之间，而 MM 在 00 和 59
之间。最早的 24 小时制时间为 00:00 ，最晚的是 23:59 。

在一步操作中，你可以将 current 这个时间增加 1、5、15 或 60 分钟。你可以执行这一操作 任意 次数。

返回将 current __ 转化为 __correct 需要的 最少操作数 。

示例 1：

**输入：** current = "02:30", correct = "04:35"
**输出：** 3
**解释：** 可以按下述 3 步操作将 current 转换为 correct ：
- 为 current 加 60 分钟，current 变为 "03:30" 。
- 为 current 加 60 分钟，current 变为 "04:30" 。 
- 为 current 加 5 分钟，current 变为 "04:35" 。
可以证明，无法用少于 3 步操作将 current 转化为 correct 。

示例 2：

**输入：** current = "11:00", correct = "11:01"
**输出：** 1
**解释：** 只需要为 current 加一分钟，所以最小操作数是 1 。

提示：

• current 和 correct 都符合 "HH:MM" 格式
• current <= correct

方法一：贪心

思路与算法

为了方便计算，我们用整数 time}_1 与 time}_2 分别表示 current 和 correct 距离 00:00 过去的分钟数，并用 diff} = \textit{time}_2 - \textit{time}_1 表示我们需要增加的分钟数。

由于我们希望增加操作的次数最少，同时对于 [1, 5, 15, 60] 这四个增加的数量，每一个数都可以整除它前面（如有）的所有元素，因此尽可能使用右边的操作替代对应次数左边的操作一定会使得操作次数更少。

我们用 res 来维护按照上述方案所需的操作数。同时，我们从大到小遍历单次操作可以增加的时间 t，则该操作可以进行的次数即为 \lfloor \textit{diff} / t \rfloor（其中 \lfloor \dots \rfloor 代表向下取整），我们将 res 加上该数值，并修改操作结束后剩余的时间差，即 diff} = \textit{diff} \bmod t。最终，res 即为最少操作次数，我们返回该数值作为答案。

代码

[sol1-C++]

class Solution {
public:
    int convertTime(string current, string correct) {
        int time1 = stoi(current.substr(0, 2)) * 60 + stoi(current.substr(3, 2));
        int time2 = stoi(correct.substr(0, 2)) * 60 + stoi(correct.substr(3, 2));
        int diff = time2 - time1;   // 需要增加的分钟数
        int res = 0;
        // 尽可能优先使用增加数值更大的操作
        vector<int> ops = {60, 15, 5, 1};
        for (int t: ops) {
            res += diff / t;
            diff %= t;
        }
        return res;
    }
};

[sol1-Python3]

class Solution:
    def convertTime(self, current: str, correct: str) -> int:
        time1 = int(current[:2]) * 60 + int(current[3:])
        time2 = int(correct[:2]) * 60 + int(correct[3:])
        diff = time2 - time1   # 需要增加的分钟数
        res = 0
        # 尽可能优先使用增加数值更大的操作
        for t in [60, 15, 5, 1]:
            res += diff // t
            diff %= t
        return res

复杂度分析

• 时间复杂度：O(1)。

• 空间复杂度：O(1)。