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 <stdio.h>
2#include <stdlib.h>
3#include <limits.h>
4
5int timeToMinutes(const char* time) {
6 int hours = (time[0] - '0') * 10 + (time[1] - '0');
7 int minutes = (time[3] - '0') * 10 + (time[4] - '0');
8 return hours * 60 + minutes;
9}
10
11int compare(const void* a, const void* b) {
12 return *((int*)a) - *((int*)b);
13}
14
15int findMinDifference(char** timePoints, int timePointsSize) {
16 int* minutes = (int*)malloc(sizeof(int) * timePointsSize);
17 for (int i = 0; i < timePointsSize; ++i)
18 minutes[i] = timeToMinutes(timePoints[i]);
19
20 qsort(minutes, timePointsSize, sizeof(int), compare);
21
22 int minDiff = INT_MAX;
23 for (int i = 1; i < timePointsSize; ++i) {
24 int diff = minutes[i] - minutes[i - 1];
25 if (diff < minDiff) minDiff = diff;
26 }
27
28 int wrapAroundDiff = minutes[0] + 1440 - minutes[timePointsSize - 1];
29 if (wrapAroundDiff < minDiff) minDiff = wrapAroundDiff;
30
31 free(minutes);
32 return minDiff;
33}
34
35int main() {
36 char* timePoints[] = {"23:59", "00:00"};
37 int size = 2;
38 printf("%d\n", findMinDifference(timePoints, size));
39 return 0;
40}
This implementation works by converting each time point to the number of minutes since 00:00. We sort these times and then calculate the adjacent differences. We also calculate the wraparound difference from the last to the first 24-hour period to ensure capturing the smallest difference across 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.
1using System.Collections.Generic;
public class MinimumTimeDifference {
private static int TimeToMinutes(string time) {
int hours = int.Parse(time.Substring(0, 2));
int minutes = int.Parse(time.Substring(3, 2));
return hours * 60 + minutes;
}
public static int FindMinDifference(IList<string> timePoints) {
bool[] minutes = new bool[1440];
foreach (var time in timePoints) {
int minute = TimeToMinutes(time);
if (minutes[minute]) return 0;
minutes[minute] = true;
}
int first = -1, last = -1, prev = -1, minDiff = 1440;
for (int i = 0; i < 1440; ++i) {
if (minutes[i]) {
if (first == -1) first = i;
if (prev != -1) minDiff = Math.Min(minDiff, i - prev);
prev = i;
last = i;
}
}
minDiff = Math.Min(minDiff, first + 1440 - last);
return minDiff;
}
public static void Main() {
List<string> timePoints = new List<string> { "23:59", "00:00" };
Console.WriteLine(FindMinDifference(timePoints));
}
}
C# uses a boolean array to track each potential minute. The minimum gap between active minutes is calculated, including the wrap-around difference.