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 ütkö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

(Nemes Tihamér 2001. döntő)