You are given two strings current
and correct
representing two 24-hour times.
24-hour times are formatted as "HH:MM"
, where HH
is between 00
and 23
, and MM
is between 00
and 59
. The earliest 24-hour time is 00:00
, and the latest is 23:59
.
In one operation you can increase the time current
by 1
, 5
, 15
, or 60
minutes. You can perform this operation any number of times.
Return the minimum number of operations needed to convert current
to correct
.
Example 1:
Input: current = "02:30", correct = "04:35" Output: 3 Explanation: We can convert current to correct in 3 operations as follows: - Add 60 minutes to current. current becomes "03:30". - Add 60 minutes to current. current becomes "04:30". - Add 5 minutes to current. current becomes "04:35". It can be proven that it is not possible to convert current to correct in fewer than 3 operations.
Example 2:
Input: current = "11:00", correct = "11:01" Output: 1 Explanation: We only have to add one minute to current, so the minimum number of operations needed is 1.
Constraints:
current
andcorrect
are in the format"HH:MM"
current <= correct
Solution: Greedy
Start with 60, then 15, 5 and finally increase 1 minute a time.
Time complexity: O(1)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Author: Huahua class Solution { public: int convertTime(string current, string correct) { auto getMinute = [](string_view t) { return (t[0] - '0') * 10 * 60 + (t[1] - '0') * 60 + (t[3] - '0') * 10 + (t[4] - '0'); }; int t1 = getMinute(current); int t2 = getMinute(correct); int ans = 0; for (int d : {60, 15, 5, 1}) while (t2 - t1 >= d) { ++ans; t1 += d; } return ans; } }; |