Scelta greedy

<aside> 💡 Un algoritmo greedy è un algoritmo che effettua ad ogni passo la scelta che in quel momento sembra la migliore (localmente ottima) nella speranza di ottenere una soluzione globalmente ottima

</aside>

Questo approccio non sempre porta ad una soluzione ottima

Interval scheduling

• input: un insieme di attività ognuna delle quali inizia ad un certo istante $s_j$ e finisce ad un certo istante $f_j$

  può essere eseguita al più un’attività alla volta

• obiettivo: trovare un sottoinsieme di cardinalità massima di job a due a due compatibili

Interval scheduling: algoritmi greedy

<aside> 💡 Considera i job in un certo ordine; ad ogni passo viene esaminato il prossimo job nell’ordinamento e se il job è compatibile con quelli scelti nei passi precedenti allora il job viene inserito nella soluzione

</aside>

L’ordinamento dipende dal criterio che si intende ottimizzare localmente

Diverse strategie basate su diversi tipi di ordinamento:

• earliest start time: considera i job in ordine crescente rispetto ai tempo di inizio $s_j$

  scelta greedy → job che inizia prima tra quelli non ancora esaminati

• earliest finish time: considera i job in ordine crescente rispetto ai tempi di fine $f_j$

  scelta greedy → job che finisce prima tra quelli non ancora esaminati

• shortest interval time: considera i job in ordine crescente rispetto alle loro durate $f_j-s_j$

  scelta greedy → job che dura meno tra quelli non ancora esaminati

• fewest conflicts: per ogni job, conta il numero $c_j$ di job che sono in conflitto con lui e ordina in modo crescente rispetto al numero di conflitti

  scelta greedy → job che ha meno conflitti tra quelli non ancora esaminati

Interval scheduling: algoritmo greedy ottimo

Analisi: $O(nlogn)$

• costo ordinamento $O(nlogn)$
• costo for $O(n)$: mantenendo traccia del tempo di fine $f$ dell’ultimo job selezionato, possiamo capire se il job $j$ è compatibile con $A$ verificando che $s_j \geq f_i$

Teorema