題目敘述 539. Minimum Time Difference
請問最小的時間差距是多少?
註:
請以分鐘為單位回答。
測試範例
Example 1:
Input: timePoints = ["23:59","00:00"]
Output: 1
Example 2:
Input: timePoints = ["00:00","23:59","00:00"]
Output: 0
約束條件
Constraints:
2 <= timePoints.length <= 2 * 10^4
輸入陣列timePoints長度介於2~兩萬。
timePoints[i]is in the format "HH:MM".
示意圖
演算法 Greedy策略 + 排序前處理
先把所有24小時制的timePoint轉成對應的minute分鐘總數。
接著排序所有時間點，從小到大排列。
如上圖所示，最小時間差值 = 相鄰的時間差距最小值。
實作上有一個細節要留意，最早時間-最晚時間的時間差也要一併考慮進去，
算是一個corner case。
60* 24 - timePoints[len(timePoints) - 1] + timePoints[0]
最後回傳最小時間差值作為答案回傳即可。
程式碼 Greedy策略 + 排序前處理
class Solution:
def toMin(self,time):
time = time.split(':')
minutes = (60*int(time[0])) + int(time[1])
return minutes
def findMinDifference(self, timePoints: List[str]) -> int:
# HH:MM to corresponding minutes
for i, time in enumerate(timePoints):
timePoints[i] = self.toMin(time)
time_gap = math.inf
# Sort timestamp in ascending order
timePoints.sort()
#calculate the closest time distance of each element except last
for i in range(0, len(timePoints) - 1):
time_gap = min(time_gap, (timePoints[i+1] - timePoints[i]))
# including corner case: 1st timestamp - last timestamp
time_gap = min(time_gap, 60* 24 - timePoints[len(timePoints) - 1] + timePoints[0])
return time_gap
複雜度分析
時間複雜度: O( n log n)
最重的成本落在排序，所需時間為O(n log n)
空間複雜度: O(1)
所用到的皆為固定尺寸臨時變數，所需空間為O(1)常數級別。
