{x}
blog image

Minimum Number of Operations to Convert Time

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 and correct are in the format "HH:MM"
  • current <= correct

Solution Explanation

This problem asks for the minimum number of operations to convert a given start time (current) to an end time (correct). We can increase the time by 1, 5, 15, or 60 minutes in each operation. The most efficient approach is a greedy algorithm.

Algorithm:

  1. Convert to Minutes: First, convert both current and correct times from HH:MM format into total minutes past midnight. This simplifies the calculations.

  2. Calculate the Difference: Find the difference (d) between the total minutes of correct and current. This represents the total minutes we need to add.

  3. Greedy Approach: Iterate through the possible increments (60, 15, 5, 1) in descending order. For each increment, divide the remaining difference (d) by the increment. This gives the number of times we can use that increment. Add this count to the total operations (ans). Update the remaining difference by taking the modulo (d %= i). This ensures we only count the operations for the largest possible increment at each step.

Time Complexity Analysis:

The time complexity is O(1). This is because the number of iterations in the loop is fixed (4 iterations for the four increments), independent of the input size. All other operations (string conversion, arithmetic) are constant-time.

Space Complexity Analysis:

The space complexity is O(1). We use a fixed number of variables to store the times, differences, and operation count, regardless of the input size.

Code Explanation (Python Example):

class Solution:
    def convertTime(self, current: str, correct: str) -> int:
        a = int(current[:2]) * 60 + int(current[3:])  #Convert current time to total minutes
        b = int(correct[:2]) * 60 + int(correct[3:])   #Convert correct time to total minutes
        ans, d = 0, b - a  # Initialize operations count and difference
        for i in [60, 15, 5, 1]: #Iterate through increments in descending order
            ans += d // i #Integer division to find how many times we can use the increment.
            d %= i  #Update the remaining difference.
        return ans

The Java, C++, and Go code follow the same logic with minor syntax differences for handling string manipulation and integer operations specific to their respective languages. The core algorithm remains the same greedy approach for optimal solution.