Merge Intervals

Przedział to zakres liczb całkowitych z początkiem i końcem. Przedziały, które mają co najmniej jeden wspólny punkt, należą do siebie, podobnie jak przedziały, które tylko się stykają: [1, 4] i [4, 5] łączą się w [1, 5]. Celem jest zastąpienie każdej grupy nakładających się przedziałów jednym przedziałem obejmującym całą grupę.

Kluczem jest kolejność. Gdy przedziały zostaną posortowane według początku, każdy przedział nakładający się na budowany przedział znajdzie się bezpośrednio za nim. Przejdź przez posortowaną listę i zapamiętuj ostatni połączony przedział: jeśli początek następnego przedziału jest nie większy niż jego koniec, przesuń koniec; jeśli nie, oznacza to rzeczywistą przerwę, więc zaczyna się nowy przedział. Sortowanie kosztuje O(n log n), a przejście wymaga tylko jednego przebiegu.

Napisz funkcję o nazwie mergeIntervals, która otrzymuje dwie tablice liczb całkowitych, starts i ends, i zwraca połączone przedziały.

Przedziały są przekazywane jako dwie tablice, ponieważ nie każdy z użytych tu języków akceptuje tablicę 2D jako dane wejściowe: przedział i to [starts[i], ends[i]], a obie tablice mają tę samą długość. Przedziały nie są posortowane.

Połącz każdą grupę nakładających się przedziałów. Przedziały, które jedynie stykają się na końcu, również uznaj za nakładające się. Zwróć połączone przedziały jako tablicę 2D [[start, end], ...], posortowaną według początku.

Na przykład starts = [5, 1, 12, 3] i ends = [7, 4, 14, 6] opisują przedziały [5, 7], [1, 4], [12, 14] i [3, 6], które po połączeniu dają [[1, 7], [12, 14]].

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