Merge Intervals

Un intervallo è un intervallo di numeri interi con un inizio e una fine. Gli intervalli che condividono almeno un punto appartengono allo stesso gruppo, così come quelli che si toccano soltanto: [1, 4] e [4, 5] diventano [1, 5]. L’obiettivo è sostituire ogni gruppo di intervalli sovrapposti con un unico intervallo che copra l’intero gruppo.

Il trucco sta nell’ordinamento. Una volta ordinati gli intervalli per punto iniziale, tutto ciò che si sovrappone all’intervallo che stai costruendo si trova subito dopo. Scorri l’elenco ordinato e mantieni l’ultimo intervallo unito: se il punto iniziale successivo è minore o uguale alla sua fine, estendi la fine; altrimenti, c’è un vero intervallo vuoto, quindi inizia un nuovo intervallo. L’ordinamento richiede O(n log n) e la scansione è un unico passaggio.

Scrivi una funzione chiamata mergeIntervals che riceve due array di interi, starts e ends, e restituisce gli intervalli uniti.

Gli intervalli sono forniti come due array perché non tutti i linguaggi qui accettano un array bidimensionale come input: l’intervallo i è [starts[i], ends[i]] e i due array hanno la stessa lunghezza. Gli intervalli non sono ordinati.

Unisci ogni gruppo di intervalli sovrapposti. Anche gli intervalli che si toccano a un estremo sono considerati sovrapposti. Restituisci gli intervalli uniti come array bidimensionale [[start, end], ...], ordinati per valore iniziale.

Per esempio, starts = [5, 1, 12, 3] e ends = [7, 4, 14, 6] descrivono [5, 7], [1, 4], [12, 14] e [3, 6], che si uniscono in [[1, 7], [12, 14]].

Vincoli: 1 <= starts.length == ends.length <= 10^4, 0 <= starts[i] <= ends[i] <= 10^4.