ALGORITMO con una determinata complessità

[LM92]

Salve gente,
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 come struttura dati per memorizzare gli intervalli.

[insideworld]

io seguirei il suggerimento verificando se il nuovo intervallo ha intersezioni con il precedente. probabilmente la soluzione comprende l'ordinare gli intervalli in ordine crescente (guardando il punto di partenza) così la seconda parte dell'algoritmo risulta più semplice.
Di che esame si tratta?

[LM92]

si hai ragione ho disturbato la professoressa per saperlo XD

la materia si chiama introduzione agli algoritmi.