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