Meeting Rooms II

Q: Какова временная сложность задачи Meeting Rooms II?

Оба быстрых решения работают за O(n log n) . Вариант с кучей сортирует встречи и выполняет одну операцию с кучей за O(log n) для каждой встречи; вариант с двумя списками выполняет две сортировки и один проход за O(n) . Оба используют дополнительную память O(n) . Подсчёт текущих встреч в момент начала каждой встречи занимает O(n²) .

СреднеИнтервалы Куча Сортировка

+10

Вам дан список встреч в виде двух массивов: встреча i проходит с starts[i] до ends[i]. В одной комнате одновременно может проходить только одна встреча, и встреча может начаться в комнате в тот же момент, когда там заканчивается другая встреча.

Напишите функцию с именем minMeetingRooms, которая возвращает наименьшее количество комнат, в которых можно провести все встречи.

Функция

minMeetingRooms(starts: integer-array, ends: integer-array) → integer

startsinteger-array: время начала каждой встречи
endsinteger-array: время окончания каждой встречи, с тем же индексом, что и время начала
Возвращаетinteger: минимальное количество комнат, в которых можно провести все встречи

Ограничения

1 ≤ starts.length == ends.length ≤ 5000
0 ≤ starts[i] < ends[i] ≤ 10⁶
Встречи не отсортированы. Две встречи могут быть одинаковыми.

Примеры

Ввод: starts = [4, 1, 7, 2]ends = [8, 5, 9, 6]
Вывод: 3
Пояснение: В момент времени 4 одновременно проходят встречи с 1 до 5, с 2 до 6 и с 4 до 8, поэтому тебе нужно как минимум 3 комнаты. Трёх достаточно: встреча с 7 до 9 занимает комнату, которая освобождается в 5.

Ввод: starts = [0, 2, 3]ends = [10, 3, 5]
Вывод: 2
Пояснение: Встреча с 0 до 10 занимает одну комнату всё это время. Для встречи с 2 до 3 нужна вторая комната, а встреча с 3 до 5 занимает эту же комнату, как только она освобождается, поэтому достаточно 2 комнат.

+17 скрытых тестов при отправке

Дополнительный вопрос

Можешь также указать, в какую комнату назначено каждое собрание, используя не больше комнат, чем указано в ответе?

Решение

Количество необходимых комнат равно наибольшему количеству встреч, проходящих одновременно. Подсчёт текущих встреч в каждый момент начала позволяет найти его за O(n²). Сортировка сводит задачу к одному проходу по дню: минимальная куча с временами освобождения комнат или два отсортированных списка времени начала и окончания дают ответ за O(n log n).

Подсчитайте количество встреч, проходящих в каждый момент начала

Верно, но не успевает на самых больших тестах

Идея

В любой момент каждому совещанию, которое сейчас проходит, нужна отдельная комната. Поэтому комнат нужно как минимум столько, сколько составляет наибольшее число совещаний, проходящих одновременно. Этого количества также достаточно: выделяйте комнаты в порядке времени начала, а новая комната понадобится только тогда, когда все комнаты заняты, то есть именно в этот момент проходит столько совещаний.

Число совещаний, проходящих одновременно, увеличивается только тогда, когда начинается совещание, поэтому самый загруженный момент — начало какого-либо совещания. Для каждого совещания i подсчитайте совещания j, для которых выполняется starts[j] ≤ starts[i] < ends[j]: они уже начались и ещё не закончились. Совещание, которое заканчивается ровно в момент starts[i], не учитывается, потому что в этот момент его комната снова свободна.

В первом примере в момент времени 4 проходят совещания с 1 до 5, с 2 до 6 и с 4 до 8: всего 3. В момент времени 7 проходят только совещания с 4 до 8 и с 7 до 9: всего 2. Наибольшее число — 3.

Для каждого из n совещаний проверяются все n совещаний. При n = 5000 это 25 миллионов проверок: доли секунды в C, несколько секунд в Python или R и в четыре раза больше с каждым удвоением n.

Алгоритм

Для каждой встречи i установите running равным 0.
Для каждой встречи j увеличьте running на 1, если starts[j] ≤ starts[i] < ends[j].
Сохраняйте наибольшее значение running, которое вы встретили.
Верните это наибольшее значение.

def minMeetingRooms(starts, ends):
    n = len(starts)
    most = 0
    for i in range(n):
        # how many meetings are running at the moment meeting i starts
        running = 0
        for j in range(n):
            if starts[j] <= starts[i] < ends[j]:
                running += 1
        most = max(most, running)
    return most

Мини-куча времени, когда комнаты освобождаются

Идея

Назначайте залы так, как это делал бы администратор на стойке регистрации. Рассматривайте встречи в порядке времени начала. Для каждой встречи посмотрите на зал, который освободится первым. Если к моменту начала встречи он свободен, встреча проходит в этом зале. Если нет, значит, все залы ещё заняты, поэтому нужно открыть новый.

Проверить только этот зал безопасно. Если зал, который освободится первым, всё ещё занят, значит, заняты и все остальные. Если он свободен, подойдёт любой свободный зал: все следующие встречи начинаются в это время или позже, поэтому любой зал, свободный сейчас, останется свободным для них.

Вам нужно знать самое раннее время освобождения зала, и оно меняется после каждой встречи. Мини-куча хранит время окончания встречи для каждого зала и возвращает наименьшее значение. При повторном использовании зала его время окончания заменяется временем окончания новой встречи; при открытии зала добавляется новое время окончания. В первом примере, если отсортировать встречи по времени начала: встреча с 1 до 5 даёт [5], встреча с 2 до 6 даёт [5, 6], встреча с 4 до 8 даёт [5, 6, 8], а встреча с 7 до 9 находит время 5, которое не позднее 7, и заменяет его, оставляя [6, 8, 9]. Три зала.

Сортировка занимает O(n log n), а для каждой встречи выполняется одна операция с кучей за O(log n). Python-овский heapq, PriorityQueue в Java, priority_queue с greater в C++, BinaryHeap с Reverse в Rust, container/heap в Go и SplMinHeap в PHP предоставляют кучу. В остальных языках её нужно хранить в массиве: родитель элемента с индексом i находится по индексу (i-1)/2, а значение перемещается вверх, пока оно меньше родительского.

Алгоритм

Отсортируй встречи по времени начала, сохраняя каждое время начала вместе с соответствующим временем окончания.
Для каждой встречи, если куча не пуста и её наименьшее время окончания меньше или равно времени начала встречи, замени это время окончания временем окончания встречи.
В противном случае добавь время окончания встречи в кучу: откроется новая комната.
Верни размер кучи — по одной записи на комнату.

import heapq


def minMeetingRooms(starts, ends):
    meetings = sorted(zip(starts, ends))  # by start time
    free_at = []  # a min-heap: when each room's last meeting ends
    for start, end in meetings:
        if free_at and free_at[0] <= start:
            heapq.heapreplace(free_at, end)  # the earliest free room is free now: reuse it
        else:
            heapq.heappush(free_at, end)  # every room is busy: open a new one
    return len(free_at)

Отсортируйте начала и окончания отдельно

Идея

Куча помнит, какое время окончания относится к какой комнате, но ответ — это только количество. Когда начинается встреча, важно лишь, закончилась ли к этому времени какая-нибудь другая встреча и освободила комнату; какая именно встреча — неважно. Поэтому отсортируйте начала и окончания в два отдельных списка и пройдитесь по началам, используя указатель ended в списке окончаний.

Для каждого начала по порядку: если оно приходится на endTimes[ended] или позже, к этому времени встреча уже закончилась. Её комнату занимает новая встреча, а ended сдвигается дальше. Иначе все используемые комнаты всё ещё заняты, и значение rooms увеличивается на единицу. Каждое начало использует не более одного окончания — так же, как повторно используемая комната в куче заменяет одно старое время окончания новым.

В первом примере начала — 1, 2, 4, 7, а окончания — 5, 6, 8, 9. Начала 1, 2 и 4 предшествуют окончанию 5, поэтому значение rooms увеличивается до 3. Начало 7 приходится на 5 или позже, поэтому оно использует ту же комнату, а ended сдвигается к окончанию 6. Ответ — 3. Знак ≥ позволяет встречам, идущим вплотную друг за другом, использовать одну комнату: во втором примере встреча начинается в 12, когда заканчивается другая, и использует её комнату.

Количество никогда не превышает истинный пик: когда значение rooms увеличивается, следующее окончание ещё впереди, поэтому в этот момент все rooms встреч проходят одновременно. Оно также достигает пика, потому что начало пропускает открытие комнаты только тогда, когда реальное окончание в это же время или раньше уже освободило её. Две сортировки требуют O(n log n), проход — O(n), а отсортированные копии занимают O(n) памяти.

Алгоритм

Отсортируй копию начала и копию окончаний.
Установи rooms и ended в значение 0.
Для каждого начала по порядку, если оно совпадает с endTimes[ended] или следует за ним, прибавь 1 к ended: встреча занимает освободившуюся комнату.
Иначе прибавь 1 к rooms.
Верни rooms.

def minMeetingRooms(starts, ends):
    start_times = sorted(starts)
    end_times = sorted(ends)
    rooms = 0
    ended = 0  # how many meetings have ended, earliest end first
    for start in start_times:
        if start >= end_times[ended]:
            ended += 1  # a meeting has ended by now: this one takes its room
        else:
            rooms += 1  # every room is busy: open a new one
    return rooms

Ловушки и крайние случаи

Большинство ошибок связано со сравнением в момент соприкосновения интервалов или с тем, какую комнату проверяют.

Проверка start > end вместо start ≥ end. Тогда встреча не может занять комнату в тот самый момент, когда она освобождается, и для встреч с 10 до 12, с 12 до 14 и с 14 до 16 требуется 2 комнаты вместо 1.
Проверка последней открытой комнаты вместо комнаты, которая освободится первой. Для встреч с 1 до 3, с 2 до 10 и с 4 до 6 последняя открытая комната занята до 10, поэтому вы открываете третью комнату, хотя первая свободна уже с 3.
Определение наибольшего числа встреч, пересекающихся с одной встречей, и прибавление единицы. Встреча с 0 до 10 пересекается со встречами с 2 до 3 и с 3 до 5, но эти две встречи не пересекаются друг с другом, поэтому достаточно 2 комнат, а не 3.
Путаница между двумя подходами с сортировкой. Для кучи каждое время окончания должно оставаться в паре со своим временем начала до сортировки по времени начала; в подходе с двумя списками времена начала и окончания намеренно сортируются отдельно.

Частые вопросы4

Какова временная сложность задачи Meeting Rooms II?

Оба быстрых решения работают за O(n log n). Вариант с кучей сортирует встречи и выполняет одну операцию с кучей за O(log n) для каждой встречи; вариант с двумя списками выполняет две сортировки и один проход за O(n). Оба используют дополнительную память O(n). Подсчёт текущих встреч в момент начала каждой встречи занимает O(n²).

Почему min-куча решает задачу Meeting Rooms II?

Рассматривая встречи в порядке времени начала, имеет смысл проверять только ту комнату, которая освободится первой. Мини-куча времени окончания позволяет получить эту комнату за O(1) и обновить кучу за O(log n). Куча растёт только тогда, когда все комнаты заняты, поэтому её итоговый размер равен минимальному числу комнат, которое подходит.

Можно ли решить задачу «Переговорные комнаты II» без кучи?

Да. Отсортируйте время начала и время окончания как два отдельных списка и проходите по времени начала, используя указатель на время окончания. Время начала, совпадающее со следующим неиспользованным временем окончания или наступающее позже него, позволяет повторно использовать комнату; любое другое время начала требует открыть новую комнату. Тот же подход работает как метод сканирующей прямой: преобразуйте каждую встречу в событие +1 в момент её начала и событие -1 в момент её окончания, обрабатывайте окончания раньше начал при совпадении времени и отслеживайте наибольшую текущую сумму.

Совпадает ли ответ с максимальным количеством встреч, которые пересекаются одновременно?

Да. Встречи, проходящие одновременно, требуют разных комнат, поэтому вам нужно как минимум столько комнат. Если назначать каждой встрече в порядке начала любую свободную комнату, больше не потребуется, поэтому максимальное число пересекающихся встреч и есть точный ответ.

Python

def minMeetingRooms(starts, ends):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

starts = [4, 1, 7, 2]
ends = [8, 5, 9, 6]

Ожидается

Meeting Rooms II

Функция

Ограничения

Примеры

Подсказки

Решение

Подсчитайте количество встреч, проходящих в каждый момент начала

Мини-куча времени, когда комнаты освобождаются

Отсортируйте начала и окончания отдельно

Ловушки и крайние случаи

Частые вопросы4

Похожие задачи