Leetcode 2224: Minimum Number of Operations to Convert Time
You are given two 24-hour formatted times,
current and correct. Each time is represented in the format ‘HH:MM’, where HH is the hour (00 to 23) and MM is the minutes (00 to 59). In one operation, you can increase the current time by 1, 5, 15, or 60 minutes. Your task is to determine the minimum number of operations required to convert the current time to the correct time.Problem
Approach
Steps
Complexity
Input: You are given two strings `current` and `correct`, both in the format 'HH:MM', where the time is represented as a 24-hour clock.
Example: current = '08:30', correct = '09:20'
Constraints:
• current and correct are in the format 'HH:MM'
• current <= correct
Output: Return the minimum number of operations needed to convert the `current` time to the `correct` time.
Example: Output: 2
Constraints:
• The input strings `current` and `correct` will always be valid 24-hour time strings.
Goal: The goal is to calculate the difference in minutes between `current` and `correct`, then apply the largest operations first (60 minutes, 15 minutes, 5 minutes, and 1 minute) to minimize the number of operations.
Steps:
• Convert the current and correct times to minutes.
• Calculate the difference between the two times in minutes.
• Iterate over the available operations (60, 15, 5, and 1 minute) to minimize the number of operations.
Goal: The input strings `current` and `correct` will always be valid and follow the 24-hour time format.
Steps:
• The strings will always be valid 24-hour formatted times.
• current is less than or equal to correct.
Assumptions:
• The time difference will always be positive or zero.
• Input: Input: current = '08:30', correct = '09:20'
• Explanation: The difference is 50 minutes. We can first add 60 minutes (to make it 09:30), and then subtract 10 minutes to reach 09:20. This requires 2 operations.
• Input: Input: current = '06:10', correct = '07:05'
• Explanation: The difference is 55 minutes. First, add 60 minutes (to make it 07:10), then subtract 5 minutes to reach 07:05. This requires 2 operations.
Approach: The approach involves converting both times into minutes, finding the difference, and applying the largest possible operations to minimize the number of steps required.
Observations:
• The time difference is key to solving this problem.
• Using the largest increments (60 minutes) first can quickly reduce the time difference.
Steps:
• Convert both `current` and `correct` times into minutes by extracting the hour and minute values.
• Calculate the time difference.
• Apply the operations (60, 15, 5, and 1 minute) in descending order of value to minimize the operations.
Empty Inputs:
• The input is guaranteed to be valid and will always contain two time strings.
Large Inputs:
• The time difference between `current` and `correct` is manageable, as no time will exceed 1440 minutes (24 hours).
Special Values:
• When `current` is equal to `correct`, the output should be 0 operations.
Constraints:
• current <= correct.
class Solution {
int getTime(string &s) {
return stoi(s.substr(0, 2)) * 60 + stoi(s.substr(3));
}
public:
int convertTime(string current, string correct) {
int diff = getTime(correct) - getTime(current), ops[4] = {60,15,5,1}, ans = 0;
for (int op : ops) {
ans += diff / op;
diff %= op;
}
return ans;
}
1 : Class Declaration
class Solution {
This is the declaration of the class `Solution`, which contains the methods to solve the problem.
2 : Function Declaration
int getTime(string &s) {
The function `getTime` is defined to convert a time string `s` into an integer representing the total minutes.
3 : Return Statement
return stoi(s.substr(0, 2)) * 60 + stoi(s.substr(3));
This line of code converts the given time string `s` (in HH:MM format) into total minutes by extracting the hours and minutes separately.
4 : Access Modifier
public:
This marks the beginning of the public section, where methods accessible outside the class will be defined.
5 : Function Declaration
int convertTime(string current, string correct) {
The `convertTime` function is defined, which takes two time strings, `current` and `correct`, and calculates the number of operations to convert one into the other.
6 : Variable Initialization
int diff = getTime(correct) - getTime(current), ops[4] = {60,15,5,1}, ans = 0;
The difference in minutes between the correct and current times is calculated. The array `ops` contains the available operation durations (60, 15, 5, and 1 minute). The variable `ans` is initialized to 0 to keep track of the number of operations.
7 : Loop
for (int op : ops) {
A for loop iterates over each operation in `ops` to calculate how many times each operation can be performed.
8 : Update Answer
ans += diff / op;
For each operation `op`, the number of times it can be applied is added to `ans`, and the difference `diff` is reduced accordingly.
9 : Update Difference
diff %= op;
After performing the division, the remainder (`diff`) is updated to reflect the remaining time that couldn't be covered by the current operation.
10 : Return Statement
return ans;
The function returns the total number of operations needed to convert the `current` time to the `correct` time.
Best Case: O(1), as only a constant number of operations are needed regardless of the time difference.
Average Case: O(1), since the number of available operations is fixed.
Worst Case: O(1), the operations do not depend on the size of the input times.
Description: The time complexity is constant because the solution always involves a fixed number of operations.
Best Case: O(1), as no additional space is required.
Worst Case: O(1), since only a few variables are used.
Description: The space complexity is constant since the solution only uses a few variables.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus