NézetNyomtat

Rendezvény (Megoldás)
Címkék > Feladat

Rendezvény

Egy kultúrháznak két nagy előadóterme van, $A$ és $B$. Egy napon sok előadást szeretnének tartani a két teremben. Az igazgató begyűjtötte az igényeket, azt, hogy ki mettől-meddig akar előadást tartani. Természetesen egy teremben egyszerre csak egy előadás tartható. Ha egy előadás az $T$ időpontban ér véget, akkor a következő előadás legkorábban a $T+1$ időpontban kezdődhet.

Feladat

Készíts programot (RENDEZ.PAS, ...), amely kiszámítja a legtöbb előadás számát, amelyek megtarthatók a két teremben! A programod adjon is meg egy beosztást a két teremre, amellyel elérhető, hogy a lehető legtöbb előadás legyen megtartva!

Bemenet

A RENDEZ.BE szöveges állomány első sorában az igényelt előadások $N$ száma van $(1\leq N\leq 1000)$. A további $N$ sor mindegyike két egész számot tartalmaz (egy szóközzel elvá­lasztva), egy igényelt előadás $K$ kezdő időpontja és $B$ befejezési időpontja $(1\leq K < B \leq 720)$. Az előadásokat a sorszámukkal azonosítjuk, az állomány $i+1$-edik sorában van az $i$-edik előadás adata.

Kimenet

A RENDEZ.KI szöveges állomány első sorába két egész számot kell írni (egy szóközzel elválasztva)! Az első szám az $A$ terembe beosztott előadások $U$ száma, a második pedig a $B$ terembe beosztott előadások $V$ száma legyen! A második sor azon előadások sorszámát tartal­mazza (egy-egy szóközzel elválasztva), amelyeket ebben a sorrendben az $A$ teremben tarta­nak! A harmadik sor azon előadások sorszámát tartalmazza (egy-egy szóközzel elválasztva), amelyeket ebben a sorrendben az $B$ teremben tartanak! Több megoldás esetén bármelyik meg­adható.

Példa

RENDEZ.BERENDEZ.KI
10
3 8
9 20
13 25
2 5
2 4
13 22
22 30
6 10
7 9
10 20
3 4
5 8 6
4 9 10 7

Tesztadatok