leetcode-759 Employee Free Time

# Given a list schedule of employees, which represents the working time for each
# employee, return the list of finite intervals representing common, positive-length
# free time for all employees.

class Solution:
    def employeeFreeTime(self, schedule: List[List[List[int]]]) -> List[List[int]]:
        # Flatten all intervals
        intervals = []
        for employee in schedule:
            for interval in employee:
                intervals.append(interval)

        # Sort by start time
        intervals.sort(key=lambda x: x[0])

        # Merge intervals
        merged = [intervals[0]]
        for interval in intervals[1:]:
            if interval[0] <= merged[-1][1]:
                merged[-1][1] = max(merged[-1][1], interval[1])
            else:
                merged.append(interval)

        # Find gaps
        free_time = []
        for i in range(1, len(merged)):
            free_time.append([merged[i-1][1], merged[i][0]])

        return free_time

# Time: O(n log n), Space: O(n)
# AirBnB: Real-world scheduling problem