Muallif: __thecrash__ 5e0ae0690ab4

B. Ishlarni rejalashtirish

Vaqt limiti: 2000 ms Xotira limiti: 256 mb

Sizda \(n\) ta ish bor. \(i\)-ish \(l_i\) vaqtda boshlanadi va \(r_i\) vaqtda tugaydi (\(l_i < r_i\)). Bir vaqtning o'zida faqat bitta ish bajarilishi mumkin — ya'ni tanlangan ishlar orasida vaqt oralig'i kesishmasligi kerak (bitta ish tugagan vaqtda boshqasi boshlansa, bu kesishish hisoblanmaydi). Maksimal nechta ishni bajarish mumkinligini toping.

Kiruvchi ma'lumotlar

Birinchi qatorda \(n\) (\(1 \le n \le 10^6\)) soni beriladi. Keyingi \(n\) ta qatorning har birida ikkita butun son \(l_i, r_i\) (\(1 \le l_i < r_i \le 10^9\)) beriladi.

Chiquvchi ma'lumotlar

Yagona qatorda — bajarish mumkin bo'lgan maksimal ishlar sonini chiqaring.

Misollar

1

4
1 3
2 5
4 7
6 8

2

2

3
1 2
2 3
3 4

3