Расписание школьной конференции

В школе идёт конференция: в разных кабинетах выступают докладчики. Ты хочешь успеть на как можно больше докладов.

Каждый доклад занимает отрезок времени: начинается в момент s и заканчивается в момент e. Если один доклад заканчивается ровно в момент, когда начинается другой, то на оба успеть можно.

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

Формат ввода

В первой строке дано целое число n — количество докладов. Далее в n строках заданы пары целых чисел s_i и e_i — начало и конец i-го доклада.

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

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

Ограничения

• 1 ≤ n ≤ 200000
• 0 ≤ s_i < e_i ≤ 1000000000
• Разрешено посещать доклады подряд, если e_a ≤ s_b.

Пример

Ввод:

5
1 3
2 5
4 7
6 9
8 10

Вывод:

3

Пояснение: можно, например, выбрать доклады [1,3], [4,7], [8,10].

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

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

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

• Прочитай все пары (s, e).
• Отсортируй доклады по e (по возрастанию). Если e одинаковые, порядок по s не важен.
• Заведи last_end — время окончания последнего выбранного доклада (сначала что-то вроде -1 или 0).
• Иди по отсортированному списку:
• если s >= last_end, значит доклад не пересекается с уже выбранными (учитывая, что e == s разрешено), добавь его в ответ и обнови last_end = e.
• Выведи счётчик выбранных докладов.

Мини-сниппет условия совместимости: if s >= last_end: take.

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

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