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