Informatika gyűjtemény

Egy szinttel feljebb Terem

2004050607080910

NézetNyomtat

Terem

Iskolád alapításának évfordulóján nagyszabású ünnepséget szervez. Egy napra sok eseményt tervez. Kiderült, hogy lesznek események, amelyek részben egy időben zajlanak. Ezért meg kell határozni, hogy legkevesebb hány termet kell előkészíteni ahhoz, hogy minden esemény számára legyen terem foglalva, és természetesen az események ne üzközzenek. Minden betervezett eseménynek ismerjük a kezdési és befejezési időpontját, amit percben adtak meg. Ha egy esemény az A perctől a B percig tart, akkor ugyanabba a terembe beosztott bármely másik esemény vagy A-nál korábban ér véget, vagy B-nél később kezdődhet.

Feladat:

Készíts programot (TEREM.PAS vagy TEREM.C), amely kiszámítja, hogy legkevesebb hány terem kell ahhoz, hogy minden betervezett eseményt meg lehessen tartani, továbbá megad egy lehetséges terembeosztást.

Bemenet:

A TEREM.BE állomány első sorában az események N száma van (1<=N<=1000). A következő N sor mindegyikében két egész szám, A és B van egy szóközzel elválasztva. Az A szám egy esemény kezdő, a B pedig ugyanezen esemény befejező időpontja (1<=A<=B<=1440)

Kimenet:

A TEREM.KI állomány első sorába az összes esemény beosztásához szükséges legkevesebb terem T számát kell írni. A következő T sorban kell megadni a termek beosztását. Egy sorba azon események sorszámait kell írni egy-egy szóközzel elválasztva, amelyek ugyanazon teremben lesznek megtartva (a különböző sorokban lévők pedig mind külön teremben).

Példa:

TEREM.BETEREM.KI
8 1100 1200 500 520 510 570 600 630 630 700 700 800 600 800 650 7004 1 2 4 8 3 5 6 7

Tesztadatok

terem0.zip (Hivatalos tesztadatok. A 7-es és a 8-as megoldása valószínűleg rossz.)
terem.zip (Javított tesztadatok.)
check.pas Ellenőrző program. Meg kell adni neki egy kimenetei és egy bemeneti fájlt és megnézi, hogy jó megoldás van-e a kimenetiben.