Объясни слияние интервалов
Вопрос
Объясни, как слить пересекающиеся интервалы, и какая сложность.
Попробуйте сами
Ответьте вслух за 2 минуты, как на собесе. Потом сверьтесь с тезисами: что прозвучало, а что нет.
Показать ответ и разбор
Коротко
Что должно прозвучать в ответе
Сортирует по началу и объясняет зачем
Сравнивает только с последним интервалом в ответе
Берёт максимум концов при слиянии
Уточняет, считаются ли касающиеся пересекающимися
O(n log n) времени, O(n) памяти на ответ
Что могут спросить следом
- Как вставить новый интервал в отсортированный список?
- Как посчитать число переговорок?
- Что если интервалы приходят потоком?
Разбор
Сортирую интервалы по началу. После этого пересечься с текущим может только последний интервал в ответе: все предыдущие уже кончились раньше. Иду по списку: если начало текущего не больше конца последнего, сливаю, причём конец беру как максимум из двух концов, ведь текущий может целиком лежать внутри. Иначе добавляю текущий как новый. Перед этим уточняю у интервьюера, сливать ли касающиеся вроде [1,3] и [3,5], от этого зависит < или <=. Сортировка O(n log n), проход O(n), память O(n) под ответ (плюс память сортировки).
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.