Programozás‎ > ‎Feladatok‎ > ‎Intervallum ütemezés‎ > ‎

Megoldás

Lehetséges mohó stratégiák

Az órai jegyzetnél említett négy lehetséges mohó stratégia közül csak egy jó.

Kezdés időpontja

Mindig a legkorábban kezdődő (és még beütemezhető) intervallumot választjuk.
Ellenpélda:


Intervallum hossza

Mindig a legrövidebb intervallumot választjuk, ami még lehetséges.
Ellenpélda:


Ütközések száma

Mindig azt az intervallumot választjuk, ami a legkevesebbel "ütközik".
Ellenpélda:

Befejezés időpontja

Mindig a legkorábban befejeződő intervallumot választjuk. Ez a választás jó megoldást ad.

A bizonyítás vázlata kiolvasható Kevin Wayne diarészleteiből. Indirekt feltesszük, hogy van egy optimális algoritmus (OPT), ami több intervallumot tud kiválasztani, mint a mohó algoritmusunk (GREEDY). Megnézzük, hol van az első olyan intervallum, amit OPT kiválasztott, de GREEDY nem. Ezt lecserélhetjük a mohó algoritmus megfelelő intervallumára, így az optimálisban következő intervallumokat a mohó is beválasztotta volna.


Kód