Розбір розв'язку

Оскільки координати ~l_i, r_i~ можуть сягати ~10^9~, будувати масив по всіх точках напряму неможливо — потрібна техніка лінії подій (sweep line) з попереднім упорядкуванням лише "цікавих" точок (їх усього ~O(n)~, на відміну від усього діапазону координат).

Ідея розв'язку:

1. Для кожного відрізка ~[l_i, r_i]~ створити дві "події": у точці ~l_i~ — подію "+1" (відрізок починається, покриття збільшується), у точці ~r_i + 1~ — подію "-1" (відрізок щойно закінчився, покриття зменшується). Важливо додавати подію саме в ~r_i+1~, а не в ~r_i~, оскільки точка ~r_i~ ще повністю покрита цим відрізком.
2. Відсортувати всі ~2n~ подій за координатою.
3. Пройти події зліва направо, підтримуючи поточну кількість покриттів (cur): для кожної координати підсумувати всі події, що трапляються саме в цій точці (можуть бути й "+1", і "-1" одночасно), і одразу оновити cur.
4. Після кожного оновлення cur порівнювати його з поточним максимумом і оновлювати відповідь.

Максимальне покриття завжди досягається рівно в точці, де починається якийсь із відрізків, тому перевіряти достатньо саме ці ~O(n)~ "цікавих" точок — немає потреби перебирати всі цілі числа від ~1~ до ~10^9~.

Складність — ~O(n \log n)~ за рахунок сортування подій, що цілком укладається в обмеження часу навіть при ~n = 2 \cdot 10^5~.