# **Leetcode筆記(Employee Free Time)** :::info :information_source: 題目 : Employee Free Time, 類型 : arrays , 等級 : hard 日期 : 2023/05/08 ::: ### 嘗試 ```python ``` --- ### **優化** 其實不用特別管哪個員工是哪個interval，因為重疊的地方部會處理到，只要注意"下個員工的上班時間比前個員工的下班時間還晚"，那就代表中間有空檔，然後要持續更新最晚擁有下班時間的那個下班時間 第一個部分的兩個for迴圈時間複雜度O(n)，因為遍歷一次，空間複雜度O(1)，因為all_intervals ```python """ Definition of Interval: class Interval(object): def __init__(self, start, end): self.start = start self.end = end """ class Solution: def employee_free_time(self, schedule: List[List[int]]) -> List[Interval]: all_intervals = [] for employee in schedule: for i in range(0, len(employee), 2): # 把每一段時間視為不同員工 all_intervals.append([employee[i], employee[i+1]]) # 重新排序 以便更新與查看下一個人上班時間 all_intervals.sort(key = lambda x : x[0]) res = [] # 一旦後一個人上班時間大於前一個人下班時間 # 代表有空檔 pre_end = all_intervals[0][1] for time in all_intervals[1:]: if time[0] > pre_end: # 記得輸出形式指定為interval(有start和end) # 故要轉成interval res.append(Interval(pre_end, time[0])) pre_end = time[1] else: pre_end = max(pre_end, time[1]) return res ``` --- **:warning: 錯誤語法** :::warning ::: **:thumbsup:學習** :::success ::: **思路** ![](https://hackmd.io/_uploads/rkpSm58N2.png) **講解連結** https://www.youtube.com/watch?v=4XiZ-mVxvbk&ab_channel=%E4%BB%8A%E5%A4%A9%E6%AF%94%E6%98%A8%E5%A4%A9%E5%8E%B2%E5%AE%B3 Provided by. 今天比昨天厲害 ###### tags: `arrays` `hard` `leetcode`