[LeetCode] Medium - 539. Minimum Time Difference

Source From Here
Question
Given a list of 24-hour clock time points in "Hour:Minutes" format, find the minimum minutes difference between any two time points in the list.
Example 1:

Input: ["23:59","00:00"]
Output: 1

Note:

* The number of time points in the given list is at least 2 and won't exceed 20000.
* The input time is legal and ranges from 00:00 to 23:59.

Solution

Naive

view plaincopy to clipboardprint?

1. from datetime import datetime  
2.   
3. class Solution:  
4.     def findMinDifference(self, timePoints: List[str]) -> int:  
5.         ts_list = list(map(lambda t: int(t[0])*60 + int(t[1]) if t[0]!='00' or t[1]!='00' else 60*24, map(lambda s:s.split(':'), timePoints)))  
6.           
7.         # max min diff = 720 happens in 00:00 - 12:00  
8.         # 00:00 - 12:01 with diff  
9.         # min( 00:00 - 12:01 = 721, 12:01 - 24:00 = 719) = 719  
10.         def time_diff(t1, t2):  
11.             td = abs(t1 - t2)  
12.             return td if td < 12 * 60 else 1440 - td  
13.           
14.         ts_list.sort()  
15.         min_td = float('inf')  
16.         ts_len = len(ts_list)  
17.         for i in range(0, ts_len):  
18.             td = time_diff(ts_list[i], ts_list[i-1])  
19.             if td < min_td:  
20.                 min_td = td  
21.                   
22.         return min_td  

Runtime: 80 ms, faster than 43.58% of Python3 online submissions for Minimum Time Difference.
Memory Usage: 15.8 MB, less than 100.00% of Python3 online submissions for Minimum Time Difference.

Discussion_1 (link)

view plaincopy to clipboardprint?

1. class Solution:  
2.     def findMinDifference(self, timePoints: List[str]) -> int:  
3.         minutes = sorted(list(map(lambda x: int(x[:2]) * 60 + int(x[3:]), timePoints)))  
4.         return min((y - x) % (24 * 60) for x, y in zip(minutes, minutes[1:] + minutes[:1]))  

From above solution, you can check below explanation:

>>> timePoints = ['05:31', '22:08', '00:35']
>>> minutes = sorted(list(map(lambda x: int(x[:2]) * 60 + int(x[3:]), timePoints)))
>>> minutes
[35, 331, 1328]

>>> minutes[1:] + minutes[:1] // shift element to left for pair diff operation
[331, 1328, 35]

>>> [(y - x) for x, y in zip(minutes, minutes[1:] + minutes[:1])] // Calculate time difference between pair element
[296, 997, -1293] // The time diff between '22:08', '00:35' should be min('00:35' -> '22:08' = 1293, '22:08' -> '00:35' = 1440 - 1293 = -1293 % 1440 = 147)

>>> -1293 % 1440
147
>>> min((y - x) % 1440 for x, y in zip(minutes, minutes[1:] + minutes[:1]))
147

Supplement
* Python 文章收集 - How To Convert Timestamp To Date and Time in Python
* FAQ - Convert string date to timestamp in Python
* Python timestamp to datetime and vice-versa