Почему это работает
- Убрать как можно меньше — то же, что оставить как можно больше. Интервал, который кончается раньше всех, всегда стоит оставить: любой другой выбор кончается позже и оставляет остальным меньше места.
- Дальше тот же выбор повторяется среди тех, что начинаются не раньше его конца. По порядку концов это один проход: интервал остаётся, если начало ≥ lastEnd, иначе он пересекает последний оставленный — убираем.
- Сортировка по началу здесь ошиблась бы: [0, 9] начинается раньше всех, и, оставив его, мы закрыли бы [1, 3], [3, 5] и [6, 8].
Сложность
Время O(n log n): сортировка; проход после неё — O(n). Память O(1), не считая того, что нужно сортировке.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗