Ütemezés
(Megoldás)
Címkék > Feladat
Versenyek > Nemes Tihamér OKSzTV > 2002 > Második forduló > 11-13. osztály
Elmélet > Algoritmusok > Mohó
Elmélet > Algoritmusok > Rendezések
Címkék > Feladat
Versenyek > Nemes Tihamér OKSzTV > 2002 > Második forduló > 11-13. osztály
Elmélet > Algoritmusok > Mohó
Elmélet > Algoritmusok > Rendezések
Ütemezés
Mekk Elek ezermester népszerű vállalkozó, sokan keresik fel megrendelésekkel. Minden megrendelt munkának ismeri a kezdési és a befejezési idejét. A mester a következő évre szóló megrendelések közül a lehető legtöbbet akarja elvállalni, de egyszerre csak egy munkán tud dolgozni.
Feladat
Írj programot (UTEMEZ.PAS, UTEMEZ.C vagy UTEMEZ.CPP néven), amely meghatározza a munkák egy lehető legnagyobb elemszámú részhalmazát úgy, hogy az összes kiválasztott munka elvégezhető legyen.
Bemenet
Az UTEMEZ.BE állomány első sora a megrendelések N számát $(1\leq N\leq 10000)$ tartalmazza. A következő N sor mindegyike két pozitív egész számot tartalmaz, a megrendelt munka K kezdési, illetve B befejezési idejét $(1\leq K\leq B\leq 365)$, tehát a J-edik munkát az állomány J+1-edik sora írja le.
Kimenet
Az UTEMEZ.KI állomány első sorában a kiválasztott munkák M száma legyen. A második sorba M számot, a kiválasztott munkák sorszámát kell írni egy-egy szóközzel elválasztva, tetszőleges sorrendben. Ha több megoldás is van, közülük egy tetszőlegeset kell kiírni.
Példa
| UTEMEZ.BE | UTEMEZ.KI |
| 6 2 3 2 4 5 7 3 4 2 2 1 2 | 3 6 3 4 |