Стрелы по шарам

В игре на фестивале по всей карте висят магические шары. Каждый шар защищён заклинанием: его можно лопнуть только если стрела прилетит по горизонтали в точку с координатой x, которая лежит внутри «окна уязвимости» шара — от l до r включительно.

У вас есть лук, но стрел мало. Одна стрела выбирает ровно одну координату x и лопает все шары, у которых l ≤ x ≤ r.

Найдите минимальное число стрел, чтобы лопнуть все шары.

Формат ввода

Первая строка: целое число n — количество шаров. Следующие n строк: по два целых числа l и r (l ≤ r) — окно уязвимости очередного шара.

Формат вывода

Выведите одно целое число — минимальное количество стрел.

Ограничения

• 1 ≤ n ≤ 20000
• 0 ≤ l, r ≤ 1000000

Пример

Ввод:

4
10 16
2 8
1 6
7 12

Вывод:

2

Ключевое наблюдение: если мы хотим одной стрелой покрыть как можно больше шаров, выгодно ставить её в «самую раннюю» точку, после которой текущий выбор уже не поможет — то есть в правую границу какого-то окна. Тогда мы не сужаем возможности для следующих шаров.

Приём: жадный выбор (greedy). Сортируем интервалы по правой границе r. Идём слева направо по этим r и поддерживаем координату cur — где стоит последняя выпущенная стрела. Если очередной шар уже не накрыт (cur < l), мы обязаны сделать новую стрелу. Лучшее место для неё — ровно r этого шара: это максимально «право», но всё ещё внутри окна, значит с наибольшим шансом зацепит будущие интервалы.

План:

• Считать n интервалов (l, r).
• Отсортировать интервалы по r (по возрастанию).
• cur = -inf, ans = 0.
• Для каждого (l, r) в этом порядке:
• если cur < l, то ans += 1 и поставить стрелу в cur = r.
• Вывести ans.

Мини-сниппет логики: if cur < l: ans += 1; cur = r

Сложность: сортировка O(n log n), проход O(n).

Частая ошибка: сортировать по l (ломает жадность) или проверять cur <= l вместо cur < l — при cur == l шар уже накрыт, новая стрела не нужна.