How does the greedy approach work in this problem?

The greedy approach starts by using the largest allowed increment (60 minutes), then progressively uses smaller increments (15, 5, and 1 minute) to reduce the difference in the minimum number of operations.

What should I do if the times are in 12-hour format instead of 24-hour format?

First, convert the 12-hour format into 24-hour time. Then, proceed with the same approach as in the problem description.

What is the time complexity of this solution?

The time complexity is O(1) because the solution involves a constant number of operations, irrespective of the size of the input times.

What if the difference between the current and correct time is zero?

If the difference is zero, no operations are needed, and the answer is 0.

Can this approach be optimized further?

The greedy approach used here is already optimal for this problem, as it minimizes the number of operations by always using the largest increments first.

#2224

Easy

auto_awesome贪心·invariant

LeetCode 题解工作台

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

给你两个字符串 current 和 correct ，表示两个 24 小时制时间。 24 小时制时间按 "HH:MM" 进行格式化，其中 HH 在 00 和 23 之间，而 MM 在 00 和 59 之间。最早的 24 小时制时间为 00:00 ，最晚的是 23:59 。在一步操作中，你可以将…

字符串贪心

题目描述

给你两个字符串 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

lightbulb

解题思路

方法一：贪心

1

2

3

4

5

6

7

8

9

10

class Solution:
    def convertTime(self, current: str, correct: str) -> int:
        a = int(current[:2]) * 60 + int(current[3:])
        b = int(correct[:2]) * 60 + int(correct[3:])
        ans, d = 0, b - a
        for i in [60, 15, 5, 1]:
            ans += d // i
            d %= i
        return ans

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate identify the correct greedy choice for minimizing operations?
question_mark
Does the candidate understand how to convert times to a simpler representation (minutes)?
question_mark
Is the candidate able to effectively implement a greedy strategy?

warning

常见陷阱

外企场景

error
Failing to convert times to minutes, which complicates the difference calculation.
error
Not choosing the largest increment first, which leads to a higher number of operations.
error
Misunderstanding the constraints, particularly the ordering of the current and correct times.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if you were allowed to decrease the current time instead of only increasing it?
arrow_right_alt
What if you could use different increments for each operation (e.g., 1, 2, 3, 4 minutes)?
arrow_right_alt
What if the times were provided in a different format, such as 12-hour time?

help

常见问题

外企场景

继续练习

#2207 字符串中最多数目的子序列 #2193 得到回文串的最少操作次数 #2259 移除指定数字得到的最大结果