Выбор ответа Middle Интервалы обновлено
Сколько нужно переговорок
Вопрос
Даны интервалы встреч. Найти минимальное число переговорок. Какой подход?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Сортировать по началу и держать min-кучу концов занятых комнат. Ответ это максимум одновременно идущих встреч.
Варианты ответа
- Слить пересекающиеся интервалы и посчитать, сколько их осталось
- Жадно брать самую длинную встречу и раскладывать остальные вокруг
- Посчитать число интервалов: каждой встрече нужна своя комната
- Сортировать по началу и держать min-кучу концов занятых комнатправильный ответ
Разбор
Ответ это максимум одновременно идущих встреч. Куча концов: если самая ранняя занятая комната освободилась к началу новой встречи, переиспользуем её. Или «события»: +1 на начало, -1 на конец, максимум префиксной суммы. O(n log n).
- Слияние теряет информацию о том, сколько встреч перекрывается.
- Длина встречи не определяет число комнат.
- Число интервалов это верхняя граница, а не минимум.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.