Задача: 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 {
    public $start;
    public $end;
    function __construct($start, $end) {
        $this->start = $start;
        $this->end = $end;
    }
}

function employeeFreeTime($schedule) {
    $intervals = [];
    foreach ($schedule as $employee) {
        $intervals = array_merge($intervals, $employee);
    }
    
    usort($intervals, function($a, $b) {
        return $a->start - $b->start;
    });
    
    $merged = [];
    foreach ($intervals as $interval) {
        if (empty($merged) || end($merged)->end < $interval->start) {
            $merged[] = $interval;
        } else {
            end($merged)->end = max(end($merged)->end, $interval->end);
        }
    }
    
    $freeTime = [];
    for ($i = 1; $i < count($merged); $i++) {
        if ($merged[$i]->start > $merged[$i - 1]->end) {
            $freeTime[] = new Interval($merged[$i - 1]->end, $merged[$i]->start);
        }
    }
    
    return $freeTime;
}

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