~/algor $ cat masalalar/tadbirlar-jadvali
Greedy-03
Tadbirlar jadvali
Muallif:
Iqbolshoh Ilhomjonov
O'rtacha
2000 ms
128 MB
45%
Bitta zalda $n$ ta tadbir o'tkazilishi rejalashtirilgan: $i$-tadbir $s_{i}$ vaqtda boshlanib, $e_{i}$ vaqtda tugaydi. Zalda bir vaqtda faqat bitta tadbir bo'lishi mumkin; bir tadbir tugagan vaqtda keyingisi boshlanishi mumkin. Eng ko'pi bilan nechta tadbirni o'tkazish mumkinligini aniqlang.
Kiruvchi ma'lumotlar
Birinchi qatorda natural son $n$. Keyingi $n$ ta qatorning har birida ikkita butun son: $s_{i}$ va $e_{i}$.
Chiquvchi ma'lumotlar
Bitta butun son — o'tkazish mumkin bo'lgan tadbirlarning eng ko'p soni.
Izoh
$1 \le n \le 10^{5}$
$0 \le s_{i} \lt e_{i} \le 10^{9}$
Misollar
Kirish #1
3 1 3 2 5 3 9
Chiqish #1
2
Kirish #2
4 1 2 2 3 3 4 1 4
Chiqish #2
3