Почему это работает
- Список отсортирован и без пересечений, поэтому делится на три куска подряд: интервалы, которые кончаются до lo, интервалы, пересекающие новый, и интервалы правее него. Сортировать не нужно.
- Каждый пересекающийся интервал расширяет [lo, hi]: минимум начал и максимум концов. Вместо всех них в результат идёт один слитый интервал, поэтому пересечений в нём нет.
- Касание считается пересечением, и знаки это учитывают: конец < lo оставляет интервал в стороне, только если он кончается раньше lo, а начало ≤ hi впускает [7, 8], хотя он только начинается в hi = 7.
Сложность
Время O(n): за три цикла каждый интервал просматривается один раз. Память O(n) на результат.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗