LeetCode 2224: Minimum Number of Operations to Convert Time (Greedy by 60/15/5/1)
LeetCode 2224GreedyStringToday we solve LeetCode 2224 - Minimum Number of Operations to Convert Time.
Source: https://leetcode.com/problems/minimum-number-of-operations-to-convert-time/
English
Problem Summary
Given two times current and correct in HH:MM format, you can increase current time by 1, 5, 15, or 60 minutes per operation. Return the minimum number of operations needed to reach correct.
Key Insight
After converting both times into total minutes, the problem becomes making up a non-negative difference diff using coin values [60, 15, 5, 1]. This set is canonical, so always taking the largest possible step is optimal.
Algorithm
- Parse current and correct into minutes.
- Compute diff = correctMin - currentMin.
- For each step in [60, 15, 5, 1], add diff / step to answer and set diff %= step.
- Return the accumulated answer.
Complexity Analysis
Time: O(1) (only 4 step sizes).
Space: O(1).
Common Pitfalls
- Parsing hour/minute incorrectly from string.
- Forgetting that operations only increase time (problem guarantees reachable target in same day order).
- Simulating minute-by-minute instead of direct greedy counting.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int convertTime(String current, String correct) {
int diff = toMinutes(correct) - toMinutes(current);
int[] steps = {60, 15, 5, 1};
int ans = 0;
for (int step : steps) {
ans += diff / step;
diff %= step;
}
return ans;
}
private int toMinutes(String t) {
int h = Integer.parseInt(t.substring(0, 2));
int m = Integer.parseInt(t.substring(3, 5));
return h * 60 + m;
}
}func convertTime(current string, correct string) int {
diff := toMinutes(correct) - toMinutes(current)
steps := []int{60, 15, 5, 1}
ans := 0
for _, step := range steps {
ans += diff / step
diff %= step
}
return ans
}
func toMinutes(t string) int {
h := int(t[0]-'0')*10 + int(t[1]-'0')
m := int(t[3]-'0')*10 + int(t[4]-'0')
return h*60 + m
}class Solution {
public:
int convertTime(string current, string correct) {
int diff = toMinutes(correct) - toMinutes(current);
vector<int> steps{60, 15, 5, 1};
int ans = 0;
for (int step : steps) {
ans += diff / step;
diff %= step;
}
return ans;
}
private:
int toMinutes(const string& t) {
int h = (t[0] - '0') * 10 + (t[1] - '0');
int m = (t[3] - '0') * 10 + (t[4] - '0');
return h * 60 + m;
}
};class Solution:
def convertTime(self, current: str, correct: str) -> int:
def to_minutes(t: str) -> int:
h = int(t[:2])
m = int(t[3:])
return h * 60 + m
diff = to_minutes(correct) - to_minutes(current)
ans = 0
for step in (60, 15, 5, 1):
ans += diff // step
diff %= step
return ansvar convertTime = function(current, correct) {
const toMinutes = (t) => {
const h = Number(t.slice(0, 2));
const m = Number(t.slice(3, 5));
return h * 60 + m;
};
let diff = toMinutes(correct) - toMinutes(current);
let ans = 0;
for (const step of [60, 15, 5, 1]) {
ans += Math.floor(diff / step);
diff %= step;
}
return ans;
};中文
题目概述
给定两个 HH:MM 格式时间 current 与 correct。每次操作可把当前时间增加 1、5、15 或 60 分钟，求最少操作次数。
核心思路
把时间转换为“总分钟数”后，问题变成用面额 [60, 15, 5, 1] 凑出差值 diff。由于这些步长满足贪心最优性质，每次优先使用最大步长即可得到最少次数。
算法步骤
- 将 current、correct 解析为分钟数。
- 计算差值 diff = correctMin - currentMin。
- 依次处理 60, 15, 5, 1：累加 diff / step，再令 diff %= step。
- 累加结果即答案。
复杂度分析
时间复杂度：O(1)（固定 4 种步长）。
空间复杂度：O(1)。
常见陷阱
- 时间字符串切片位置写错。
- 忘记题目是“只允许增加时间”。
- 用逐分钟模拟，导致实现冗长且不必要。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int convertTime(String current, String correct) {
int diff = toMinutes(correct) - toMinutes(current);
int[] steps = {60, 15, 5, 1};
int ans = 0;
for (int step : steps) {
ans += diff / step;
diff %= step;
}
return ans;
}
private int toMinutes(String t) {
int h = Integer.parseInt(t.substring(0, 2));
int m = Integer.parseInt(t.substring(3, 5));
return h * 60 + m;
}
}func convertTime(current string, correct string) int {
diff := toMinutes(correct) - toMinutes(current)
steps := []int{60, 15, 5, 1}
ans := 0
for _, step := range steps {
ans += diff / step
diff %= step
}
return ans
}
func toMinutes(t string) int {
h := int(t[0]-'0')*10 + int(t[1]-'0')
m := int(t[3]-'0')*10 + int(t[4]-'0')
return h*60 + m
}class Solution {
public:
int convertTime(string current, string correct) {
int diff = toMinutes(correct) - toMinutes(current);
vector<int> steps{60, 15, 5, 1};
int ans = 0;
for (int step : steps) {
ans += diff / step;
diff %= step;
}
return ans;
}
private:
int toMinutes(const string& t) {
int h = (t[0] - '0') * 10 + (t[1] - '0');
int m = (t[3] - '0') * 10 + (t[4] - '0');
return h * 60 + m;
}
};class Solution:
def convertTime(self, current: str, correct: str) -> int:
def to_minutes(t: str) -> int:
h = int(t[:2])
m = int(t[3:])
return h * 60 + m
diff = to_minutes(correct) - to_minutes(current)
ans = 0
for step in (60, 15, 5, 1):
ans += diff // step
diff %= step
return ansvar convertTime = function(current, correct) {
const toMinutes = (t) => {
const h = Number(t.slice(0, 2));
const m = Number(t.slice(3, 5));
return h * 60 + m;
};
let diff = toMinutes(correct) - toMinutes(current);
let ans = 0;
for (const step of [60, 15, 5, 1]) {
ans += Math.floor(diff / step);
diff %= step;
}
return ans;
};
Comments