Merge Intervals
Otrzymujesz zestaw przedziałów, z których każdy obejmuje liczby całkowite od początku do końca. Połącz każdą grupę nakładających się przedziałów w jeden przedział obejmujący całą grupę i zwróć połączone przedziały posortowane według początku. Przedziały, które tylko się stykają, takie jak [1, 4] i [4, 5], uznaje się za nakładające się.
Przedziały są przekazywane jako dwie tablice o tej samej długości: przedział i to [starts[i], ends[i]]. Zwracasz tablicę 2D, czyli listę par [start, end].
Funkcja
- startsinteger-array
- początek każdego przedziału
- endsinteger-array
- koniec każdego przedziału, pod tym samym indeksem co jego początek
- Zwracainteger-2d-array
- połączone przedziały jako pary [start, end], posortowane według początku
Ograniczenia
1 ≤ starts.length == ends.length ≤ 1040 ≤ starts[i] ≤ ends[i] ≤ 104- Przedziały pojawiają się w dowolnej kolejności.
- Przedziały, które stykają się tylko końcami, uznaje się za nakładające się.
Przykłady
- Wejście
- starts = [5, 1, 12, 3]ends = [7, 4, 14, 6]
- Wyjście
- [[1, 7], [12, 14]]
- Wyjaśnienie
- W kolejności rozpoczęcia [1, 4] nakłada się na [3, 6], które nakłada się na [5, 7], więc te trzy przedziały tworzą [1, 7]. [12, 14] zaczyna się po 7 i pozostaje osobno.
- Wejście
- starts = [6, 1]ends = [9, 6]
- Wyjście
- [[1, 9]]
- Wyjaśnienie
- Przedziały to [6, 9] i [1, 6]. Mają wspólny punkt 6, a stykanie się liczy się jako nakładanie, więc łączą się w [1, 9].
Pytanie dodatkowe
Przedziały są już scalone i posortowane według początku, a Ty musisz dodać jeden nowy przedział. Czy potrafisz zwrócić scaloną listę w czasie O(n), bez ponownego sortowania?
Podpowiedzi
Otwieraj je po kolei. Każda zdradza trochę więcej.
Najpierw połącz każdy początek z jego końcem, aby pracować na całych przedziałach zamiast na dwóch osobnych tablicach.
Posortuj przedziały według początku. Po tym przedział może nachodzić tylko na bezpośrednio poprzedzającą go grupę, nigdy na dalszą.
Przejdź po posortowanych przedziałach, przechowując ostatni scalony przedział. Jeśli początek następnego jest mniejszy lub równy jego końcowi, ustaw jego koniec na większy z tych dwóch końców. W przeciwnym razie ta grupa jest zakończona, a następny przedział rozpoczyna nową.
Rozwiązanie
Łączenie par w dowolnej kolejności wymaga wielokrotnego przechodzenia, ponieważ każde połączenie poszerza przedział i pozwala mu dosięgnąć przedziałów, które zostały już sprawdzone. Zamiast tego posortuj przedziały według początku. Wtedy przedział może nakładać się tylko na grupę, którą tworzysz, a jedno przejście wystarczy, by zakończyć zadanie.
Scalaj nakładające się pary, aż nic się nie zmieni
Poprawne, ale nie kończy się na największych testach
Intuicja
Przedziały [a, b] i [c, d] nakładają się, gdy c ≤ b i a ≤ d, a [min(a, c), max(b, d)] obejmuje oba. Każde scalenie usuwa jeden przedział, więc proces się kończy, a gdy pełny przebieg nie wykryje nakładania, żadne dwa pozostałe przedziały nie mają wspólnego punktu. Jeden przebieg nie wystarczy: scalony przedział jest szerszy i może teraz sięgać przedziału, z którym wcześniej w przebiegu porównywano jego mniejszą część.
Jeden przebieg porównuje około n²/2 par, a może być potrzebnych nawet n przebiegów: O(n³). Jeden przebieg po 10^4 przedziałach to już 5 × 10^7 porównań.
Algorytm
- Skopiuj
startsiends, a także przechowuj liczbęnaktywnych przedziałów. - Porównaj każdy przedział
iz każdym późniejszym przedziałemj. Jeśli się nakładają, rozszerzi, aby obejmowałj, przenieś ostatni aktywny przedział do komórkiji zmniejszno jeden. - Po scaleniu ponownie sprawdź komórkę
j, ponieważ znajduje się w niej teraz inny przedział. - Powtarzaj przebiegi, aż żaden z nich nie spowoduje scalenia.
- Połącz każdy aktywny początek z jego końcem, posortuj pary według początku i zwróć je.
def mergeIntervals(starts, ends):
s = list(starts)
e = list(ends)
n = len(s)
changed = True
while changed:
changed = False
i = 0
while i < n:
j = i + 1
while j < n:
if s[j] <= e[i] and s[i] <= e[j]:
# Intervals i and j overlap: interval i absorbs interval j.
s[i] = min(s[i], s[j])
e[i] = max(e[i], e[j])
# Move the last interval into slot j and drop the last slot.
n -= 1
s[j] = s[n]
e[j] = e[n]
changed = True
else:
j += 1
i += 1
return sorted([s[k], e[k]] for k in range(n))Posortuj według początku i wykonaj jedno przejście
Intuicja
Po posortowaniu według początku kolejny przedział zaczyna się nie wcześniej niż jakikolwiek przedział w ostatniej grupie, która kończy się na e. Jeśli jego początek jest nie większy niż e, pokrywa się z grupą lub jej dotyka, więc do niej dołącza, a e przyjmuje większą z tych dwóch wartości końcowych. Jeśli zaczyna się za e, żaden późniejszy przedział również nie może sięgnąć wstecz do tej grupy, ponieważ kolejne przedziały zaczynają się dalej na prawo. Grupa jest zakończona, a przedział otwiera nową.
Sortowanie kosztuje O(n log n), a przegląd odwiedza każdy przedział raz. Grupy są zamykane od lewej do prawej, więc wynik jest posortowany według początku.
Algorytm
- Połącz każdy początek z jego końcem: przedział
ito[starts[i], ends[i]]. - Posortuj pary według początku.
- Przejdź po posortowanych parach. Jeśli wynik jest pusty lub para zaczyna się po końcu ostatniego scalonego przedziału, dodaj ją jako nowy przedział.
- W przeciwnym razie ustaw koniec ostatniego scalonego przedziału na większą z wartości: jego koniec lub koniec pary.
- Zwróć scaloną listę.
def mergeIntervals(starts, ends):
intervals = sorted(zip(starts, ends))
merged = []
for start, end in intervals:
if merged and start <= merged[-1][1]:
if end > merged[-1][1]:
merged[-1][1] = end
else:
merged.append([start, end])
return merged
Pułapki i przypadki brzegowe
- Porównywanie z
<zamiast≤. Stykające się przedziały, takie jak[1, 4]i[4, 5], muszą zostać scalone. - Ustawianie końca na końcu nowego przedziału zamiast na większej z tych dwóch wartości.
[1, 10], po którym następuje[2, 3], musi pozostać[1, 10]. - Sortowanie samych
starts, a następnie odczytywanieendsna nowych pozycjach, przez co początek otrzymuje koniec innego przedziału. Najpierw połącz je w pary albo posortuj indeksy. - Porównywanie z poprzednim przedziałem wejściowym zamiast z ostatnim scalonym. W przypadku
[1, 10],[2, 3],[4, 5]trzeci przedział leży wewnątrz[1, 10], mimo że nie styka się z[2, 3]. - W C nieustawienie
*returnSizena liczbę scalonych przedziałów oraz rozmiaru każdej kolumny na 2.
Najczęstsze pytania3
Jaka jest złożoność czasowa problemu łączenia przedziałów?
Rozwiązanie polegające na sortowaniu i przeglądaniu przedziałów działa w czasie O(n log n) dla n przedziałów: sortowanie kosztuje O(n log n), a przeglądanie O(n). Wykorzystuje O(n) dodatkowej pamięci na posortowane pary i wynik.
Dlaczego sortować przedziały według początku, a nie końca?
Po posortowaniu według początku przedział może nakładać się tylko na grupę, którą tworzysz, więc jedno porównanie z końcem tej grupy rozstrzyga wszystko. Po posortowaniu według końca późniejszy przedział może zaczynać się przed grupami, które zostały już zamknięte: [5, 6] występuje przed [1, 10], a przeglądanie do przodu błędnie zachowałoby 5 jako początek.
Czy możesz scalać przedziały bez dodatkowego miejsca?
Tak, jeśli możesz zmienić dane wejściowe. Posortuj przedziały w miejscu, a następnie zapisuj każdy scalony przedział na początku tej samej tablicy i przechowuj indeks ostatniego zapisanego przedziału. Złożoność czasowa pozostaje O(n log n), a jedyną dodatkową przestrzenią jest ta wykorzystywana przez sortowanie w Twoim języku.
Podobne zadania
Zadania oparte na tych samych pomysłach. Rozwiązanie dwóch lub trzech utrwala schemat.
def mergeIntervals(starts, ends):
# Wpisz kod tutajTest #1
Test #2
Argumenty
starts = [5, 1, 12, 3] ends = [7, 4, 14, 6]
Oczekiwany wynik
[[1, 7], [12, 14]]