Посетители ресторана

В ресторан пришли $n$ посетителей: $i$-й вошёл в момент $a_i$ и ушёл в момент $b_i$. Посетитель, ушедший в момент $b_i$, не считается находящимся вместе с тем, кто вошёл в этот же момент. Какое наибольшее число посетителей было в ресторане одновременно?

В первой строке $n$ ($1 \le n \le 2 \cdot 10^5$). В следующих $n$ строках $a_i$ и $b_i$ ($1 \le a_i < b_i \le 10^9$).

Одно число — наибольшее число посетителей одновременно.

Метод сканирующей прямой (sweep line): каждый посетитель даёт два события — $(a_i, +1)$ и $(b_i, -1)$. Отсортируйте события по времени; при равном времени уход ($-1$) идёт раньше прихода ($+1$). Складывая события по порядку, получаем текущее число людей в ресторане — его максимум и есть ответ.

Это $O(n \log n)$. Проверка каждого момента времени не работает при временах до $10^9$. В примере с $3$ до $4$ в ресторане $2$ человека.

Источник: CSES, задача 1619.