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