Задача: 759. Employee Free Time
Сложность: hard

Нам дан список 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⃣Найдите промежутки между объединенными интервалами, представляющие свободное время.

😎 Решение:

class Interval {
    var start: Int
    var end: Int
    init(_ start: Int, _ end: Int) {
        self.start = start
        self.end = end
    }
}

func employeeFreeTime(_ schedule: [[Interval]]) -> [Interval] {
    var intervals = [Interval]()
    for employee in schedule {
        intervals.append(contentsOf: employee)
    }
    
    intervals.sort { $0.start < $1.start }
    
    var merged = [Interval]()
    for interval in intervals {
        if merged.isEmpty || merged.last!.end < interval.start {
            merged.append(interval)
        } else {
            merged.last!.end = max(merged.last!.end, interval.end)
        }
    }
    
    var freeTime = [Interval]()
    for i in 1..<merged.count {
        if merged[i].start > merged[i-1].end {
            freeTime.append(Interval(merged[i-1].end, merged[i].start))
        }
    }
    
    return freeTime
}

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