Masala #KEBS1F4IKV

Xotira 32 MB Vaqt 1000 ms Qiyinchiligi 1 %

#Ochko'z algoritm

Eng kam nuqtalar soni

n ta interval [li, ri] berilgan. Minimal nechta nuqta tanlash kerakki, har bir interval kamida bitta nuqtani qamrab olsin.

Kiruvchi ma'lumotlar:

Birinchi qatorda n intervallar soni. (0 < n < 100000). Keyingi n ta qatorda li va ri lar probel bilan ajratilgan holda beriladi. (0 < li < ri < 1000000).

Chiquvchi ma'lumotlar:

Masalani javobini chop eting.

Misollar

#	input.txt	output.txt
1	4 1 3 2 5 3 6 7 8	2

Izoh:

1-testda quyidagi nuqtalar tanlab olinishi mumkin edi: {3, 8} yoki {3, 7}. Chunki har bir intervalda ushbu sonlarning kamida bittasi mavjud hamda bu eng minimal yechim.

Telegram Facebook

Yechimini yuborish

Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin