Merge Intervals

Ein Intervall ist ein Bereich ganzer Zahlen mit einem Anfang und einem Ende. Intervalle, die mindestens einen Punkt gemeinsam haben, gehören zusammen, ebenso Intervalle, die sich nur berühren: [1, 4] und [4, 5] werden zu [1, 5]. Ziel ist es, jede Gruppe überlappender Intervalle durch ein Intervall zu ersetzen, das die gesamte Gruppe abdeckt.

Der Trick ist die Reihenfolge. Sobald die Intervalle nach ihrem Anfang sortiert sind, folgt alles, was sich mit dem Intervall überschneidet, das du gerade bildest, direkt darauf. Durchlaufe die sortierte Liste und behalte das zuletzt zusammengeführte Intervall im Blick: Liegt der nächste Anfang höchstens an dessen Ende, erweitere das Ende; andernfalls gibt es eine echte Lücke, also beginnt ein neues Intervall. Das Sortieren kostet O(n log n), und das Durchlaufen erfolgt in einem einzigen Durchgang.

Schreibe eine Funktion namens mergeIntervals, die zwei ganzzahlige Arrays, starts und ends, entgegennimmt und die zusammengeführten Intervalle zurückgibt.

Die Intervalle werden als zwei Arrays übergeben, da nicht jede hier verwendete Sprache ein 2D-Array als Eingabe akzeptiert: Intervall i ist [starts[i], ends[i]], und beide Arrays haben dieselbe Länge. Die Intervalle sind nicht sortiert.

Fasse alle Gruppen überlappender Intervalle zusammen. Intervalle, die sich nur an einem Ende berühren, gelten ebenfalls als überlappend. Gib die zusammengeführten Intervalle als 2D-Array [[start, end], ...] zurück, nach Start sortiert.

Zum Beispiel beschreiben starts = [5, 1, 12, 3] und ends = [7, 4, 14, 6] die Intervalle [5, 7], [1, 4], [12, 14] und [3, 6], die zu [[1, 7], [12, 14]] zusammengeführt werden.

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