759. Employee Free Time - cocoder39/coco39_LC GitHub Wiki

759. Employee Free Time

line sweep https://github.com/cocoder39/coco39_LC/wiki/Line-Sweep

class Solution:
    def employeeFreeTime(self, schedule: '[Interval](/cocoder39/coco39_LC/wiki/Interval)') -> '[Interval]':
        events = []
        for intervals in schedule:
            for interval in intervals:
                events.append([interval.start, interval.end])
        events.sort()

        merged = []
        for start, end in events:
            if not merged or start > merged[-1][1]:
                merged.append([start, end])
            else:
                merged[-1][1] = max(merged[-1][1], end)
        
        res = []
        for i in range(1, len(merged)):
            interval = Interval(merged[i-1][1], merged[i][0])
            res.append(interval)
        return res

Optimization 1: We can build the result without actually merging intervals

class Solution:
    def employeeFreeTime(self, schedule: '[Interval](/cocoder39/coco39_LC/wiki/Interval)') -> '[Interval]':
        intervals = []
        for s in schedule:
            for interval in s:
                intervals.append(interval)
        intervals.sort(key = lambda interval: (interval.start, interval.end))
        
        lastEnd = intervals[0].end
        res = []
        for i in range(1, len(intervals)):
            if intervals[i].start > lastEnd:
                res.append(Interval(lastEnd, intervals[i].start))
            lastEnd = max(lastEnd, intervals[i].end)
        return res

Optimization 2: Suppose there are K employees, and each employee has N intervals. Instead of sorting K * N intervals (O(KN*logKN)), we apply sort to each employee's intervals and then compare among the k employees (like merge k sorted list) so the time complexity is reduced to O(NlogK)

class Solution:
    def employeeFreeTime(self, schedule: '[Interval](/cocoder39/coco39_LC/wiki/Interval)') -> '[Interval]':
        minHeap = []
        for i, s in enumerate(schedule):
            minHeap.append((s[0].start, s[0].end, i, 0))
        heapq.heapify(minHeap)
        
        lastEnd = minHeap[0][1]
        res = []
        while minHeap:
            start, end, employeeIdx, intervalIdx = heapq.heappop(minHeap)
            if start > lastEnd:
                res.append(Interval(lastEnd, start))
            lastEnd = max(lastEnd, end)
            if intervalIdx + 1 < len(schedule[employeeIdx]):
                nextInterval = schedule[employeeIdx][intervalIdx+1]
                heapq.heappush(minHeap, (nextInterval.start, nextInterval.end, employeeIdx, intervalIdx+1))
        return res