Leetcode: 759. Employee Free Time

Problem Statement

• Blackbox: You solved a similar problem with intervals where you used a Stack to compute the answer, and I solved a problem to create a sorted list from a list of sorted lists (Leetcode: 23. Merge k Sorted Lists).
• Can we pre-process the input in a way to make easy to solve the problem? We can create a list of all intervals sorted by start time. This will help us to process all of them as they come.
• How can we extend the solution for \(i\) to \(i+1\)? Be \(a\) an array with all intervals sorted by start time. We know that if there is a time off, it will definitely start after \(a[0].end\). If \(a[1].start > a[0].end\), then there is a time off from \((a[0].end, a[1].start)\). If \(a[1].start \leq a[0].end\), then the time off might start at \(\max(a[0].end, a[1].end)\). This property holds for all intervals. Therefore, we can keep a variable with the last end time and use it to create a new interval if needed or update it. Time complexity is \(O(n \log m)\) where \(m\) is the total number of intervals, because we use a Priority-Queue to get the next interval sorted by start time. Space complexity is \(O(m)\).

"""
# 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]":
        last = None
        ans = []
        for i in merge(*schedule, key=lambda i: (i.start, i.end)):
            if last is None:
                last = i.end
            elif i.start <= last:
                last = max(last, i.end)
            else:
                ans.append(Interval(last, i.start))
                last = i.end
        return ans