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 <= correctThe basic idea is to convert both 'current' and 'correct' times into the total number of minutes from the start of the day ('00:00'). Then, calculate the difference in minutes. Utilize the largest increments first (60, 15, 5, and 1), minimizing the total number of operations required to reach the target time.
In this implementation, we convert the 'current' and 'correct' times into total minutes. The remaining difference is minimized using the largest minute operation possible, proceeding in decreasing order of minute increments.
C++
Java
Python
C#
JavaScript
Time complexity: O(1), since the calculations are based on constant operations.
Space complexity: O(1), since no additional space is needed apart from a few variables.
Although dynamic programming is not required for such a small, constant problem, a conceptualization might involve formulating transitions of states as the minimal number of operations from 'current' to 'correct'. Each state would represent a specific minute alteration with a transition cost of 1, showcasing the application of dynamic programming principles for problem solving.
This pseudo-code highlights the limitations of using dynamic programming due to the simplicity and constraints of the problem, suggesting greedy solutions as more efficient for implementation.
C++
Java
Python
C#
JavaScript
Time complexity: Hypothetically O(N) where N is the minutes between current and correct.
Space complexity: O(N), but this is impractical for the given problem size.
| Approach | Complexity |
|---|---|
| Greedy Approach with Minutes Conversion | Time complexity: O(1), since the calculations are based on constant operations. |
| Dynamic Programming Approach | Time complexity: Hypothetically O(N) where N is the minutes between current and correct. |
Minimum Number of Operations to Make Array Continuous - Leetcode 2009 - Python • NeetCodeIO • 18,440 views views
Watch 9 more video solutions →Practice Minimum Number of Operations to Convert Time with our built-in code editor and test cases.
Practice on FleetCode