539. Minimum Time Difference
1. Description
Given a list of 24-hour clock time points in “HH:MM” format, return the minimum minutes difference between any two time-points in the list.
2. Example
Example 1:
Input: timePoints = [“23:59”,“00:00”]
Output: 1
Example 2:
Input: timePoints = [“00:00”,“23:59”,“00:00”]
Output: 0
3. Constraints
- 2 <= timePoints.length <= $2 * 10^4$
- timePoints[i] is in the format “HH:MM”.
4. Solutions
Sorting
n = timePoints.size()
Time complexity: O(nlogn)
Space complexity: O(n)
class Solution {
public:
int findMinDifference(const vector<string> &timePoints) {
if (timePoints.size() > 60 * 24) {
return 0;
}
auto time_copy = timePoints;
sort(time_copy.begin(), time_copy.end());
int result = get_minutes_diff_(time_copy.front(), time_copy.back());
for (int i = 1; i < time_copy.size(); ++i) {
result = min(result, get_minutes_diff_(time_copy[i - 1], time_copy[i]));
if (result == 0) {
return 0;
}
}
return result;
}
private:
inline int get_minutes_diff_(const string &time1, const string &time2) {
// suppose time2 > time1
int time_diff = ((time2[0] - time1[0]) * 10 + time2[1] - time1[1]) * 60 +
((time2[3] - time1[3]) * 10 + time2[4] - time1[4]);
return time_diff < 30 * 24 ? time_diff : 60 * 24 - time_diff;
}
};