Restoran mijozlari

Restoranga $n$ ta mijoz keldi: $i$-mijoz $a_i$ vaqtda kirib, $b_i$ vaqtda chiqib ketdi. $b_i$ vaqtda chiqqan mijoz shu vaqtda kirgan mijoz bilan birga hisoblanmaydi. Restoranda bir vaqtning o'zida eng ko'pi bilan nechta mijoz bo'lgan?

Birinchi qatorda $n$ ($1 \le n \le 2 \cdot 10^5$). Keyingi $n$ ta qatorda $a_i$ va $b_i$ ($1 \le a_i < b_i \le 10^9$).

Bitta son — bir vaqtdagi mijozlarning eng ko'p soni.

Sweep line: har bir mijozdan ikki hodisa — $(a_i, +1)$ va $(b_i, -1)$. Hodisalarni vaqt bo'yicha saralang; vaqtlar teng bo'lsa, chiqish ($-1$) kirishdan ($+1$) oldin keladi. Hodisalarni ketma-ket qo'shib borsangiz, joriy qiymat restorandagi odamlar soni bo'ladi — uning maksimumi javob.

Bu $O(n \log n)$. Har bir vaqt nuqtasini alohida tekshirish $10^9$ gacha bo'lgan vaqtlarda ishlamaydi. Misolda $3$ dan $4$ gacha restoranda $2$ kishi bor.

Manba: CSES, 1619-masala.