Причалы в час пик

В прибрежном городе запустили речные трамвайчики. У набережной есть несколько одинаковых причалов. Если два трамвайчика одновременно хотят стоять у одного причала — начинается хаос.

Каждый рейс занимает причал на полуинтервале времени [a, b): с момента a включительно и до момента b не включая b. Это значит, что если один рейс заканчивается ровно в момент t, а другой начинается ровно в момент t, то они могут использовать один и тот же причал.

Нужно понять, сколько причалов достаточно, чтобы расписание точно работало.

Формат ввода

В первой строке дано целое число n — количество рейсов. Далее в n строках записаны пары целых чисел a_i и b_i — время начала и конца рейса.

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

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

Ограничения

• 2 ≤ n ≤ 35000
• 0 ≤ a_i < b_i ≤ 1000000000

Пример

Ввод:

5
1 4
2 6
4 7
5 8
3 5

Вывод:

3

Ключевое наблюдение: сколько причалов нужно, зависит только от того, сколько рейсов одновременно занимают набережную. Если в какой-то момент пересекаются 3 рейса, меньше чем 3 причала не хватит; если максимум пересечений равен 3, то 3 достаточно.

Приём: события (sweep line). Вместо проверки всех пар интервалов превращаем каждый рейс [a, b) в два события: «пришёл» (+1) в момент a и «ушёл» (-1) в момент b. Идём по времени слева направо, поддерживаем текущую занятость и берём максимум.

Важно из-за полуинтервала [a, b): в момент b рейс уже не занимает причал, значит при одинаковом времени события должны обрабатываться так: уход раньше прихода.

План:

• Считать все пары (a, b).
• Создать массив событий: (a, +1) и (b, -1).
• Отсортировать события по времени, а при равном времени — по delta так, чтобы -1 шло раньше +1 (например, по ключу (t, delta)).
• Пройти по событиям: cur += delta, обновлять ans = max(ans, cur).
• Вывести ans.

Сложность: сортировка 2n событий, итого O(n log n) по времени и O(n) по памяти.

Частая ошибка: перепутать порядок при равных временах и посчитать, что рейс, начинающийся в t, конфликтует с рейсом, заканчивающимся в t. Проверь, что при t сначала идёт (-1), потом (+1).