Почему это работает
- После сортировки по началу за интервалом, который начинается правее конца последней группы, идут только интервалы, начинающиеся ещё правее. Ни один из них не дотянется назад до группы, поэтому группа идёт подряд.
- Поэтому каждый интервал сравниваем только с последним в результате: если он начинается не позже его конца — сливаем, иначе он открывает новую группу.
- Конец становится максимумом двух концов, а не просто новым концом: [10, 11] лежит внутри [9, 12], и его конец обрезал бы интервал.
Сложность
Время O(n log n): сортировка; проход после неё — O(n). Память O(n) на результат и то, что нужно сортировке.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗