Employee Free Time

Problem

We are given a list schedule of employees, which represents the working time for each employee.

Each employee has a list of non-overlapping Intervals, and these intervals are in sorted order.

Return the list of finite intervals representing common, positive-length free time for all employees, also in sorted order.

(Even though we are representing Intervals in the form [x, y], the objects inside are Intervals, not lists or arrays. For example, schedule[0][0].start = 1, schedule[0][0].end = 2, and schedule[0][0][0] is not defined). Also, we wouldn't include intervals like [5, 5] in our answer, as they have zero length.

Thought Process

• This question is really similar to merge intervals except instead of merging them we find where they do not overlap

Solution

"""
# 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]':
        
        if not schedule:
            return []
        
        intervals = []
        
        for employee in schedule:
            for interval in employee:
                intervals.append([interval.start, interval.end])
        
        result = []
        #or you can just do the normal sort function
        intervals.sort(key = lambda x:x[0])
        print(intervals)

        lastEnd = intervals[0][1] 
        for i in range(1, len(intervals)):
            currStart = intervals[i][0]
            currEnd = intervals[i][1]
            if currStart > lastEnd:
                result.append(Interval(lastEnd, currStart))
            lastEnd = max(lastEnd, currEnd)
        
        return result

Time Complexity

• Time: O(n log n) because we have to sort the intervals

• Space: O(n) since we're storing intervals