Partizionamento di intervalli

<aside> 💡 In questo caso disponiamo di più risorse identiche tra di loro e vogliamo che vengano svolte tutte le attività in modo tale da usare il minor numero di risorse e tenendo conto del fatto che due attività non possono usufruire della stessa risorsa allo stesso tempo

</aside>

Durante il suo svolgimento, ciascuna attività necessita di un’unica risorsa; una risorsa può essere allocata ad al più un’attività alla volta

• input: consiste in un insieme di $n$ intervalli $[s_1,f_1],..[s_n,f_n]$ che rappresentano gli intervalli durante i quali si svolgono le $n$ attività
• obiettivo: far svolgere le $n$ attività utilizzando il minor numero possibile di risorse e in modo che ciascuna risorsa utilizzata venga allocata ad al più un’attività alla volta

Partizionamento di intervalli: limite inferiore alla soluzione ottima

Immaginiamo di disporre gli intervalli lungo l’asse delle ordinate in modo da non avere due intervalli che si sovrappongono alla stessa altezza

<aside> 💡 La profondità di un insieme di intervalli è il numero massimo di intervalli intersecabili con una singola linea verticale che si muove lungo l’asse delle ascisse

</aside>

Osservazione: numero di risorse necessarie ≥ profondità

Partizionamento di intervalli: algoritmo greedy

Osservazione: l’algoritmo greedy non assegna mai la stessa risorsa a due intervalli incompatibili

Analisi: $O(nlogn)$

• per ogni risorsa $p$, manteniamo il tempo di fine più grande tra quelli degli intervalli assegnati fino a quel momento a $p$; indichiamo questo tempo con $k_p$

• usiamo una coda a priorità di coppie della forma $(p,k_p)$, dove $p$ è una risorsa già allocata e $k_p$ è l’istante fino al quale è occupata (in questo modo l’elemento con chiave minima indica la risorsa $v$ che si rende disponibile per prima)

• se $s_j \geq k_v$ allora l’intervallo $j$ può essere allocata la risorsa $v$

  in questo caso cancelliamo $v$ dalla coda e la reinseriamo con chiave $k_v = f_j$

  in caso contrario allochiamo una nuova risorsa e la inseriamo nella coda associandole la chiave $f_j$

• se usiamo una coda a priorità implementata con heap binario, ogni operazione sulla coda richiede $O(logm)$, dove $m$ è la profondità dell’insieme di intervalli

• poichè vengono fatte $O(n)$ operazioni di questo tipo, il costo complessivo del for è $O(nlogm)$

• a questo va aggiunto il costo dell’ordinamento che è $O(nlogn)$

• siccome $m \leq n$ il costo dell’algoritmo è $O(nlogn)$