ez valami rejtett oldal volt... FG,2007
Megoldás
A megoldásom mohó. Rendezi az eseményeket kezdőidőpont szerint, aztán elkezdi őket termekbe osztani: egy esemény mindig egy olyan terembe kerül, amiben még nem ütközik az addig beosztott eseménykkel. Ha nincs ilyen, akkor felveszünk egy új termet. Bizonyítható, hogy így legfeljebb annyi terem fog kelleni, amekkora az a legnagyobb esemény-részhalmaz, amelyikben bármely két esemény ütközik. (Más szavakkal a halmaz összes eseménye lefed egy időpontot.) Legyen ez a szám T. Biz: tegyük fel, hogy már felvettünk T termet, és a következő E eseményt egyik terembe sem lehet beosztani, mert mindegyik teremből ütközik valamelyik eseménnyel. Legyen ezeknek a halmaza X. Mivel a rendezés miatt E esemény kezdődött a legrégebben, ez csak úgy lehetséges, hogy E kezdőpontjában az X halmaz összes eseménye tartott még. Így az X+E halmaza T+1 elemű és minden eseménye lefedi az E kezdőpontja időpontot.
Hegység
Lehet brutál módon csinálni: feljegyezzük minden mezőre, hogy milyen hosszú az onnan induló leghosszabb emelkedő út. Ez kezdetben minden mezőre 0, de aztán elkezdjük egy ciklusban végigsöpörni a térképet: ha olyan mezőt találunk, aminek van magasabb szomszédja, akkor ha a magasabb szomszédból induló út hossza + 1 nagyobb a mezőre írt értéknél, akkor növeljük azt. Mindezt addig kell ismételgetni, amíg egy söprés idején egy növelés sem történt, ekkor már minden mezőn a leghosszabb emelkedő út hossza lesz feljegyezve. Ezek közül kell kiválasztani egy maximálisat.
Nembrutál módszer: megkeressük azokat a mezőket, amiknek nincs náluk magasabb szomszédjuk. (Leghosszabb út vége csak ilyen mező lehet.) Ezekből a csúcsokból kiindulva mélységi bejárással bejárjuk a lejtős utakat, minden mezőjükre felírjuk a távolságot. Akkor kell dönteni, ha egy csúcsból kiindulva a lejtős út összeágazik egy másik csúcs lejtős útjával. Ilyenkor akkor kell továbbmenni, ha az előzőleg feljegyzett távolságoknál nagyobbak kerülhetnek a közös lejtőre. Ezek a távolság valójában az adott mezőből induló leghosszabb emelkedő utak hosszai. Ezek közül kell kiválasztani egy maximálisat.
(Lehet, hogy még ez sem az igazi, pl. a szivat.be megszivatja.)
