Meeting Rooms II

Leetcode #253 | Medium | Куча | Интервалы

Идея

Идея завести min heap, важное замечание в этой задаче - номера комнат нам не важны, важен результат
Сортируем по началу отрезка
Идем по ним, если в heap ничего нет - кладем конец отрезка, если heap не пуст, то смотрим на него, если элемент heap меньше либо равен началу отрезка, то пересечения нет, удаляем элемент хипа и добавляем конец отрезка, если есть пересечение, то просто добавляем конец отрезка. Таким образом на вершине кучи всегда будет комната которая освободиться в мин момент времени
В конце возвращаем размер кучи

Big-O

• Время O(Nlog(N))
• Память O(N)

Код

class Solution {
    public int minMeetingRooms(List<Interval> intervals) {
        if (intervals == null || intervals.isEmpty()) return 0;
        intervals.sort((a, b) -> a.start - b.start);
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (Interval i : intervals) {
            if (!heap.isEmpty() && i.start >= heap.peek()) heap.poll();
            heap.offer(i.end);
        }
        return heap.size();
    }
}