Sponsored
Convert the time into minutes from "00:00", sort, then find the smallest difference between any two adjacent times while also considering the difference across midnight.
Time Complexity: O(n log n) due to sorting where n is the number of time points. Space Complexity: O(n) since we store the times in minutes.
1#include <iostream>
2#include <vector>
3#include <algorithm>
4#include <climits>
5
6using namespace std;
7
8int timeToMinutes(const string& time) {
9 int hours = stoi(time.substr(0, 2));
10 int minutes = stoi(time.substr(3, 2));
11 return hours * 60 + minutes;
12}
13
14int findMinDifference(vector<string>& timePoints) {
15 vector<int> minutes;
16 for (const auto& time : timePoints) {
17 minutes.push_back(timeToMinutes(time));
18 }
19
20 sort(minutes.begin(), minutes.end());
21
22 int minDiff = INT_MAX;
23 for (int i = 1; i < minutes.size(); ++i) {
24 minDiff = min(minDiff, minutes[i] - minutes[i - 1]);
25 }
26
27 int wrapAroundDiff = minutes[0] + 1440 - minutes.back();
28 minDiff = min(minDiff, wrapAroundDiff);
29
30 return minDiff;
31}
32
33int main() {
34 vector<string> timePoints = {"23:59", "00:00"};
35 cout << findMinDifference(timePoints) << endl;
36 return 0;
37}
In this C++ version, we use the same method of converting times to minutes. The function creates a vector of minutes, sorts it, and finds the minimum difference between consecutive times, including the interaction over midnight.
Mark each minute of the day in a boolean array once any time point corresponds to it. Then traverse the array to find the smallest gap between marked minutes, considering wrap-around. This is efficient because it eliminates the need for sorting.
Time Complexity: O(n + M), where M is 1440, the number of minutes in a day, n is the length of list.
Space Complexity: O(M), M = 1440, fixed.
1
In Java, a boolean array denotes occupied minutes. By looping through this array, we compute the minimum interval between marked times and include the midnight crossover.