Merge Intervals

Un intervalle est une plage de nombres entiers avec un début et une fin. Les intervalles qui partagent au moins un point vont ensemble, tout comme ceux qui se touchent : [1, 4] et [4, 5] deviennent [1, 5]. Le but est de remplacer chaque groupe d’intervalles qui se chevauchent par un seul intervalle couvrant tout le groupe.

L’astuce, c’est l’ordre. Une fois les intervalles triés par début, tout intervalle qui chevauche celui que tu construis vient juste après. Parcours la liste triée et conserve le dernier intervalle fusionné : si le début suivant est inférieur ou égal à sa fin, étends la fin ; sinon, il y a un véritable espace, donc un nouvel intervalle commence. Le tri coûte O(n log n) et le parcours se fait en un seul passage.

Écris une fonction nommée mergeIntervals qui reçoit deux tableaux d’entiers, starts et ends, et renvoie les intervalles fusionnés.

Les intervalles sont fournis sous forme de deux tableaux, car tous les langages présentés ici n’acceptent pas un tableau à 2 dimensions en entrée : l’intervalle i est [starts[i], ends[i]], et les deux tableaux ont la même longueur. Les intervalles ne sont pas triés.

Fusionne chaque groupe d’intervalles qui se chevauchent. Les intervalles qui se touchent à une extrémité sont également considérés comme se chevauchant. Renvoie les intervalles fusionnés sous forme de tableau à 2 dimensions [[start, end], ...], triés par début.

Par exemple, starts = [5, 1, 12, 3] et ends = [7, 4, 14, 6] décrivent [5, 7], [1, 4], [12, 14] et [3, 6], qui fusionnent en [[1, 7], [12, 14]].

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