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