Others
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.
Constraints:
2 <= timePoints.length <= 2 * 10**4timePoints[i]is in the format “HH:MM”.
Example 1
Input: timePoints = ["23:59","00:00"]
Output: 1
Example 2
Input: timePoints = ["00:00","23:59","00:00"]
Output: 0
A couple of key points are:
Other than that, nothing is special. Sort the minutes array and compare time difference to next time. The problem asks the minimum time difference, so a comparison of two adjacent values is enough after sorting. The tricky part is a time might be next day’s time. To handle this, the solution here added a time which is the minimum + 24 * 60 minutes. When the loop is over, the minimum difference is there.
class MinimumTimeDifference {
public:
int findMinDifference(vector<string>& timePoints) {
auto timeToMins = [](const string &t) {
return stoi(t.substr(0, 2)) * 60 + stoi(t.substr(3, 2));
};
vector<int> points;
for (auto &t : timePoints) {
points.push_back(timeToMins(t));
}
sort(points.begin(), points.end());
points.push_back(points[0] + 24 * 60);
int min_diff = 24 * 60 + 1;
for (int i = 1; i < points.size(); ++i) {
min_diff = min(min_diff, points[i] - points[i - 1]);
}
return min_diff;
}
};
class MinimumTimeDifference:
def findMinDifference(self, timePoints: List[str]) -> int:
def timeToMins(t):
return int(t[0:2]) * 60 + int(t[3:5])
points = sorted([timeToMins(t) for t in timePoints])
points.append(points[0] + 24 * 60)
min_diff = float('inf')
for i in range(1, len(points)):
min_diff = min(min_diff, points[i] - points[i - 1])
return min_diff
# @param {String[]} time_points
# @return {Integer}
def find_min_difference(time_points)
points = time_points.map {|time| time_to_mins(time)}.sort
points << points[0] + 24 * 60
min_diff = 24 * 60 + 1
(1...points.size).each do |i|
min_diff = [min_diff, points[i] - points[i - 1]].min
end
min_diff
end
def time_to_mins(s)
s[0, 2].to_i * 60 + s[3, 2].to_i
end
O(n * log(n))O(n)