Lehetséges mohó stratégiákAz órai jegyzetnél említett négy lehetséges mohó stratégia közül csak egy jó. Kezdés időpontjaMindig a legkorábban kezdődő (és még beütemezhető) intervallumot választjuk. Ellenpélda: Intervallum hosszaMindig a legrövidebb intervallumot választjuk, ami még lehetséges. Ellenpélda: Ütközések számaMindig 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. |