Programozás‎ > ‎Feladatok‎ > ‎

Intervallum ütemezés

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