Задача: 253. Meeting Rooms II
Сложность: medium

Дан массив интервалов времени встреч intervals, где intervals[i] = [starti, endi]. Верните минимальное количество необходимых конференц-залов.

Пример:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2

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

1⃣Отсортируйте встречи по времени их начала и инициализируйте мин-кучу с временем окончания первой встречи.

2⃣Для каждой последующей встречи проверьте, свободна ли комната (сравните время начала встречи с минимальным временем окончания в куче):
Если свободна, обновите время окончания этой комнаты.
Если не свободна, добавьте новое время окончания в кучу.

3⃣После обработки всех встреч размер кучи будет равен минимальному количеству необходимых комнат.

😎 Решение:

class Solution {
    function minMeetingRooms($intervals) {
        usort($intervals, function($a, $b) {
            return $a[0] - $b[0];
        });
        $heap = new SplMinHeap();
        $heap->insert($intervals[0][1]);
        
        for ($i = 1; $i < count($intervals); $i++) {
            if ($intervals[$i][0] >= $heap->top()) {
                $heap->extract();
            }
            $heap->insert($intervals[$i][1]);
        }
        return $heap->count();
    }
}

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