Dvorana
Za dvoranu je stiglo N prijava. Svaki događaj ima početak i kraj. Događaj koji počinje točno kad drugi završi smije se održati. Koliko najviše događaja možemo prihvatiti?
- Ulaz
U prvom retku N. U svakom od sljedećih N redaka početak i kraj jednog događaja.
- Izlaz
Najveći broj događaja.
- Ograničenja
1 ≤ N ≤ 100 000, 0 ≤ početak < kraj ≤ 10⁹
Primjer 1
Ulaz
5 1 4 3 5 0 6 5 7 8 9
Izlaz
3
Zapeo si?
Prvo pokušaj sam. Savjeti se otvaraju jedan po jedan, svaki otkriva malo više.
Pohlepno, ali po čemu? Isprobaj na primjeru: po početku, po trajanju, po kraju.
Događaj možeš uzeti samo ako ne smeta zadnjem uzetom.