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.BE | TEREM.KI |
| 8
1100 1200
500 520
510 570
600 630
630 700
700 800
600 800
650 700 | 4
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.
