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.
1using System;
2using System.Collections.Generic;
3
4public class MinimumTimeDifference {
5 private static int TimeToMinutes(string time) {
6 int hours = int.Parse(time.Substring(0, 2));
7 int minutes = int.Parse(time.Substring(3, 2));
8 return hours * 60 + minutes;
9 }
10
11 public static int FindMinDifference(IList<string> timePoints) {
12 List<int> minutes = new List<int>();
13 foreach (var time in timePoints) {
14 minutes.Add(TimeToMinutes(time));
15 }
16
17 minutes.Sort();
18
19 int minDiff = int.MaxValue;
20 for (int i = 1; i < minutes.Count; ++i) {
21 minDiff = Math.Min(minDiff, minutes[i] - minutes[i - 1]);
22 }
23
24 int wrapAroundDiff = minutes[0] + 1440 - minutes[minutes.Count - 1];
25 minDiff = Math.Min(minDiff, wrapAroundDiff);
26
27 return minDiff;
28 }
29
30 public static void Main() {
31 List<string> timePoints = new List<string> { "23:59", "00:00" };
32 Console.WriteLine(FindMinDifference(timePoints));
33 }
34}
In C#, we create a method to convert times to total minutes, sort those minutes, and evaluate the minimum difference between consecutive elements, including the wrap-around diff.
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.