Mohó Márton vállalkozó ismét egy
pályázaton meghirdetett munkák között válogat. Ismeri minden munka
kezdési és befejezési idejét. Egyszerre mindig csak egy munkával foglalkozhat.
Feladat
Írjunk programot, ami megadja, hogy legfeljebb hány munkát tud Mohó Márton elvállalni. Adjuk is meg az elvégezhető munkák sorszámát!
Bemenet
A bemenet első sora a lehetséges munkák N darabszámát adja meg, 1 <= N <= 10000. Ezután N sorban a munkák kezdési és befejezési ideje olvasható, 1<=K<=B<=365. Az i. munka után akkor szabad elkezdeni a j. munkát, ha Bi < Kj.
Kimenet
Az első sorba az elvégezhető munkák lehetséges maximális számát kell kiírni, majd a következő sorba egy optimális vállaláshoz tartozó munkák sorszámát.
Példa
Bemenet |
Kimenet |
12 1 20 1 15 1 17 1 12 1 10 1 19 5 30 7 30 11 30 9 30 8 30 10 30
| 2 5 9
|
14 1 5 3 4 2 10 2 15 18 23 8 18 1 2 11 15 15 25 29 30 27 29 22 28 8 24 2 9
| 5 7 2 8 5 11
|
Tesztadatok
Címkék
A feladat forrása: saját feladat
Algoritmusok: mohó algoritmus
|