Merge Intervals

Um intervalo é uma faixa de números inteiros com um início e um fim. Intervalos que compartilham pelo menos um ponto pertencem juntos, assim como intervalos que apenas se tocam: [1, 4] e [4, 5] se tornam [1, 5]. O objetivo é substituir cada grupo de intervalos sobrepostos por um único intervalo que cubra todo o grupo.

O truque está na ordem. Depois que os intervalos são ordenados pelo início, tudo o que se sobrepõe ao intervalo que você está construindo vem logo depois dele. Percorra a lista ordenada e mantenha o último intervalo mesclado: se o próximo início for menor ou igual ao seu fim, estenda o fim; caso contrário, há uma lacuna de verdade, então começa um novo intervalo. A ordenação custa O(n log n), e a varredura é uma única passagem.

Escreva uma função chamada mergeIntervals que recebe dois arrays de inteiros, starts e ends, e retorna os intervalos mesclados.

Os intervalos são fornecidos como dois arrays porque nem todas as linguagens aqui aceitam um array 2D como entrada: o intervalo i é [starts[i], ends[i]], e os dois arrays têm o mesmo comprimento. Os intervalos não estão ordenados.

Mescle cada grupo de intervalos sobrepostos. Intervalos que apenas se tocam em uma extremidade também são considerados sobrepostos. Retorne os intervalos mesclados como um array 2D [[start, end], ...], ordenados pelo início.

Por exemplo, starts = [5, 1, 12, 3] e ends = [7, 4, 14, 6] descrevem [5, 7], [1, 4], [12, 14] e [3, 6], que se mesclam em [[1, 7], [12, 14]].

Restrições: 1 <= starts.length == ends.length <= 10^4, 0 <= starts[i] <= ends[i] <= 10^4.