759. Employee Free Time.md

759. Employee Free Time (Hard)

Algorithm: Scan Line, deque, use an maxEnd varable

• add everything to a heapq
• or using deque but need to be sorted beforing adding.
• use an end variable to track. when any start time is less than this end time, update this end time to be the current slot end time.

"""
# Definition for an Interval.
class Interval:
    def __init__(self, start: int = None, end: int = None):
        self.start = start
        self.end = end
"""

class Solution:
    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':
        ans = []
        scheduleHeap = []
        for onePerson in schedule:
            for oneInterval in onePerson:
                scheduleHeap.append(oneInterval)
        scheduleHeap.sort(key = lambda x:x.start)
        # print(scheduleHeap[0].start)
        maxEnd = scheduleHeap[0].end
        scheduleHeap = deque(scheduleHeap)
        while scheduleHeap :
            currentInterval = scheduleHeap.popleft()
            print(f"{currentInterval.start}, {currentInterval.end}")
            if currentInterval.start <= maxEnd:
                if maxEnd < currentInterval.end:
                    maxEnd = currentInterval.end
                print(maxEnd)
            else:
                curEnd = currentInterval.end
                currentInterval.end = currentInterval.start
                currentInterval.start = maxEnd
                ans.append(currentInterval)
                maxEnd = curEnd
        return ans