ho un piccolo problema, sto cercando da ieri di risolvere un esercizio inerente la progettazione di un algoritmo, ma non riesco a capire come potrei procedere.
Sono riuscito a trovare una soluzione iterativa, ma la complessità è dunque molto superiore a quella richiesta.
Leggendo la traccia riesco solo ad ipotizzare che debba usare un algoritmo ricorsivo, ma non saprei proprio come strutturarlo.
qui di seguito il testo dell' esercizio:
Dati n intervalli della retta reale, si descriva un algoritmo che calcoli la lunghezza della loro unione in O(n log n) passi. Per esempio, la lunghezza dell’ intervallo [1, 3] è 2, la lunghezza dell’unione dei quattro intervalli [1, 3], [6, 9], [2, 4.5] e [7, 8] è 6.5. Si spieghi la correttezza dell’algoritmo descritto e se ne analizzi il tempo di esecuzione asintotico.
Suggerimento: utilizzare un array di coppie <inizio, fine> come struttura dati per memorizzare gli intervalli.
ho disturbato la professoressa per saperlo XD