Клубный марафон

В школе устроили «клубный марафон»: в течение дня проходят разные занятия (кружки, встречи, тренировки). Ты хочешь успеть на как можно больше занятий целиком.

Каждое занятие задано двумя числами s и t — оно начинается в момент s и заканчивается в момент t. Считай, что занятие занимает полуинтервал [s, t): если одно занятие заканчивается ровно в момент t, то на другое, начинающееся в момент t, ты успеваешь.

Нужно узнать, сколько занятий максимум можно посетить, если посещать их по очереди и не пересекаться по времени.

Формат ввода

Первая строка: целое число n — количество занятий. Далее n строк: по два целых числа s и t.

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

Выведите одно целое число — максимальное количество занятий, которые можно посетить.

Ограничения

• 2 ≤ n ≤ 35000
• 0 ≤ s < t ≤ 1_000_000_000

Пример

Ввод:

5
1 3
3 5
0 6
5 7
8 9

Вывод:

4

Пояснение: можно выбрать занятия [1,3), [3,5), [5,7), [8,9).

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

Почему жадность работает: если вы в какой-то момент выбираете занятие, которое заканчивается позже, вы не расширяете возможности, а только сужаете их (раньше освобождённое время никогда не мешает). Значит, всегда можно заменить любой выбор на занятие с более ранним окончанием и не ухудшить ответ.

План решения:

• Считайте все пары (s, t).
• Отсортируйте занятия по возрастанию t (время окончания). Если t одинаковые — порядок не важен.
• Держите last_end — конец последнего выбранного занятия.
• Идите по отсортированному списку:
• если текущее начинается не раньше last_end, то берём его: if s >= last_end: ans += 1; last_end = t.
• иначе пропускаем (оно пересекается с уже выбранным).
• Выведите ans.

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

Частая ошибка: перепутать условие непересечения для полуинтервалов [s, t). Здесь занятие, начинающееся ровно в last_end, разрешено, поэтому нужно s >= last_end, а не s > last_end.