← Natrag na lekciju 28 · Pohlepni algoritmi (greedy)

Dvorana

Lekcija 28 · Python vrijeme: 1,0 s memorija: 256 MB

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.

Rješenje

Za predaju rješenja se prijavi.