#hard
Задача: 759. Employee Free Time

Нам дан список schedule of employees, который представляет собой рабочее время каждого сотрудника. У каждого сотрудника есть список непересекающихся интервалов, и эти интервалы расположены в отсортированном порядке. Верните список конечных интервалов, представляющих общее свободное время положительной длины для всех сотрудников, также в отсортированном порядке. (Хотя мы представляем интервалы в форме [x, y], объекты внутри них являются интервалами, а не списками или массивами. Например, schedule[0][0].start = 1, schedule[0][0].end = 2, а schedule[0][0][0] не определено).Также мы не будем включать в наш ответ интервалы типа [5, 5], так как они имеют нулевую длину.

Пример:

Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3,4]]

👨‍💻 Алгоритм:

1⃣Объедините все интервалы всех сотрудников в один список и отсортируйте его по начальным временам.

2⃣Объедините пересекающиеся интервалы в один.

3⃣Найдите промежутки между объединенными интервалами, представляющие свободное время.

😎 Решение:

from typing import List

class Interval:
    def __init__(self, start: int, end: int):
        self.start = start
        self.end = end

def employeeFreeTime(schedule: List[List[Interval]]) -> List[Interval]:
    intervals = []
    for employee in schedule:
        intervals.extend(employee)
    
    intervals.sort(key=lambda x: x.start)
    
    merged = []
    for interval in intervals:
        if not merged or merged[-1].end < interval.start:
            merged.append(interval)
        else:
            merged[-1].end = max(merged[-1].end, interval.end)
    
    free_time = []
    for i in range(1, len(merged)):
        if merged[i].start > merged[i-1].end:
            free_time.append(Interval(merged[i-1].end, merged[i].start))
    
    return free_time

Ставь 👍 и забирай 📚 Базу знаний