Programozás‎ > ‎Feladatok‎ > ‎

Ü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, 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<=N<=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<=K<=B<=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

Bemenet  Kimenet
6
2 3
2 4
5 7
3 4
2 2
1 2
3
6 3 4


Tesztadatok

Címkék

A feladat forrása: Nemes Tihamér OKITV 2002, 2. forduló, 11-13. évfolyam
Algoritmusok: mohó algoritmus

megoldás