Kemune

Snorkes jaunkundzes rīkotajā deju vakarā piedalās n ķipariņi un n laumiņas.
Katras laumiņas pievilcību raksturo kāds naturāls skaitlis (jo lielāks skaitlis, jo
laumiņa tiek uzskatīta par pievilcīgāku), i-jai laumiņai viņas pievilcību
apzīmēsim ar pi. Katru ķipariņu savukārt raksturo naturālu skaitļu intervāls
[ai,bi]: ķipariņš ir parāk iedomīgs, lai dejotu ar laumiņām, kuru pievilcība ir
mazāka par ai, un pārak kautrīgs, lai dejotu ar laumiņām, kuru pievilcība ir
lielāka par bi. Uzrakstīt algoritmu, kas laikā O(n log n) noskaidro lielāko
iespējamo pāru skaitu, kas var piedalīties vienā dejā (pieņemot, ka dejas laikā
pāri nemainās).