Boda Szilárd weblapja

Aktivitás-kiválasztás
Pistike egy nyári táborba megy, ahol minden nap különböző aktivitások vannak. Tudjuk minden aktivitás kezdeti és befejezési idejét.
Írjunk egy C++ programot, amely segít Pistikének, hogy a lehető legtöbb aktivitásban részt tudjon venni!

Példa

Bemenet

start[] = {14, 15, 16, 13, 17};
finish[] = {16, 18, 17, 15, 18};
activity[] = {1, 2, 3, 4, 5};

Kimenet

4 3 5

Magyarázat:
Tipikus mohó (greedy) feladat. A feladatmegoldás lépései:

A tömböket a befejezési idő alapján növekvő sorrendbe rendezzük
Az első aktivitást mindig kiírjuk
Az ezutáni aktivitásokat akkor írjuk ki, ha a kezdeti idejük ugyanakkor, vagy később van, mint az utoljára kiválasztott aktivitásnak