Insert Interval

Q: Jaka jest złożoność czasowa wstawiania przedziału?

Rozwiązanie jednoprzejściowe działa w czasie O(n) : każdy przedział jest kopiowany lub scalany dokładnie raz. Wynik zawiera maksymalnie n+1 przedziałów, więc zajmuje O(n) pamięci, a nic innego nie zwiększa się wraz z rozmiarem danych wejściowych. Dodanie przedziału i ponowne sortowanie zajmuje natomiast O(n log n) .

Q: Czym Insert Interval różni się od Merge Intervals?

Merge Intervals zaczyna się od nieposortowanej listy, w której dowolny przedział może nakładać się na inny, dlatego najpierw trzeba ją posortować. W Insert Interval lista jest już posortowana, a stare przedziały nigdy się nie stykają, więc tylko nowy przedział może spowodować scalenie. Przedziały, z którymi się scala, tworzą jeden nieprzerwany ciąg, dlatego wystarczy jedno przejście bez sortowania.

Q: Jak sprawdzić, czy dwa przedziały nakładają się na siebie?

Przedziały [a, b] i [c, d] mają co najmniej jeden wspólny punkt dokładnie wtedy, gdy a ≤ d i c ≤ b . Oznacza to, że stykające się przedziały, takie jak [2, 4] i [4, 8] , są uznawane za nakładające się, czego wymaga to zadanie. Jeśli stykające się przedziały miałyby pozostać rozłączne, zamiast tego użyłbyś a < d i c < b .

Q: Czy wyszukiwanie binarne może przyspieszyć wstawianie przedziału?

Wyszukiwanie binarne znajduje początek i koniec połączonego ciągu w czasie O(log n) , ponieważ zarówno początki, jak i końce są posortowane. Funkcja nadal jednak zwraca nową listę, a skopiowanie do niej niezmienionych przedziałów kosztuje O(n) . Całość pozostaje więc w O(n) . Wyszukiwanie binarne się opłaca, gdy przedziały znajdują się w strukturze, która może usuwać i wstawiać zakres bez kopiowania, takiej jak zrównoważone drzewo.

ŚredniePrzedziały

+10

Otrzymujesz listę przedziałów posortowanych według początku, podaną jako dwie tablice o tej samej długości: przedział i to [starts[i], ends[i]]. Żadne dwa z nich nie nakładają się ani nie stykają. Otrzymujesz też jeden nowy przedział, [newStart, newEnd]. Wstaw go, scal z każdym przedziałem, z którym się nakłada lub styka, i zwróć wszystkie przedziały jako tablicę 2D par [start, end], posortowanych według początku.

Dwa przedziały stykają się, gdy jeden kończy się tam, gdzie zaczyna się drugi, tak jak [2, 4] i [4, 8]; stykające się przedziały łączą się w jeden. [1, 2] i [3, 4] nie mają wspólnych punktów, więc pozostają rozdzielone.

Funkcja

insertInterval(starts: integer-array, ends: integer-array, newStart: integer, newEnd: integer) → integer-2d-array

startsinteger-array: początek każdego przedziału, w kolejności rosnącej
endsinteger-array: koniec każdego przedziału, odpowiadające mu początki
newStartinteger: początek przedziału do wstawienia
newEndinteger: koniec przedziału do wstawienia
Zwracainteger-2d-array: przedziały po wstawieniu jako pary [start, end], posortowane według początku

Ograniczenia

1 ≤ starts.length == ends.length ≤ 2000
0 ≤ starts[i] ≤ ends[i] ≤ 10⁵
ends[i] < starts[i+1]: przedziały są posortowane według początku i żadne dwa z nich nie nakładają się ani nie stykają.
0 ≤ newStart ≤ newEnd ≤ 10⁵

Przykłady

Wejście: starts = [1, 5, 10, 15]ends = [3, 7, 12, 18]newStart = 6newEnd = 11
Wyjście: [[1, 3], [5, 12], [15, 18]]
Wyjaśnienie: [6, 11] nakłada się na [5, 7] i [10, 12], więc te trzy przedziały łączą się w [5, 12]. [1, 3] kończy się przed 6, a [15, 18] zaczyna się po 12, więc oba pozostają bez zmian.

Wejście: starts = [2, 8]ends = [4, 9]newStart = 4newEnd = 8
Wyjście: [[2, 9]]
Wyjaśnienie: [4, 8] styka się z [2, 4] w punkcie 4, a z [8, 9] w punkcie 8. Stykanie się liczy się jako nakładanie, więc wszystkie trzy łączą się w [2, 9].

Wejście: starts = [1, 9]ends = [2, 10]newStart = 5newEnd = 6
Wyjście: [[1, 2], [5, 6], [9, 10]]
Wyjaśnienie: [5, 6] znajduje się w przerwie między 2 a 9 i nie styka się z żadnym z sąsiadów, więc wstawia się między nie i nic się nie łączy.

+20 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Załóżmy, że wstawiasz wiele nowych przedziałów, jeden po drugim, do tej samej listy. Jak przechowywać przedziały, aby każde wstawienie kosztowało O(log n) plus jeden krok za każdy stary przedział, który pochłania?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Stare przedziały są już rozdzielone i uporządkowane, więc tylko nowy przedział może spowodować scalenie. Dzieli to listę na trzy grupy: przedziały, które kończą się przed początkiem nowego, przedziały, które nachodzą na niego lub stykają się z nim, oraz przedziały, które zaczynają się po jego końcu. Skopiuj pierwszą grupę, scal przedziały z drugiej grupy w jeden przedział, a następnie skopiuj ostatnią grupę. Jedno przejście, bez sortowania.

Dodaj to i ponownie połącz wszystko

Intuicja

Jeśli udało Ci się rozwiązać zadanie Merge Intervals, możesz wykorzystać to rozwiązanie tutaj. Dodaj nowy przedział do listy, posortuj wszystkie n+1 przedziały według początku i scal je. Po sortowaniu przedział może nakładać się tylko na grupę bezpośrednio przed nim, więc przechodzisz przez listę, przechowując ostatni scalony przedział. Gdy kolejny początek jest równy końcowi tego przedziału lub znajduje się przed nim, przesuń koniec. W przeciwnym razie występuje rzeczywista luka i zaczyna się nowy przedział.

Przeanalizuj to na pierwszym przykładzie. Lista przyjmuje postać [1, 3], [5, 7], [6, 11], [10, 12], [15, 18]. [1, 3] pozostaje osobno, ponieważ 5 jest większe od 3. 6 jest mniejsze lub równe 7, więc [5, 7] rozszerza się do [5, 11]. 10 jest mniejsze lub równe 11, więc przedział rozszerza się do [5, 12]. 15 jest większe od 12, więc [15, 18] rozpoczyna nowy przedział.

To rozwiązanie jest poprawne i działa szybko dla 2000 przedziałów. Pomija jednak dwa fakty, które zostały Ci podane: lista jest już posortowana, a stare przedziały nigdy się ze sobą nie scalają. Płacenie O(n log n) za ponowne sortowanie listy, która jest nieposortowana tylko w jednym miejscu, to krok, którego usunięcia zażąda od Ciebie osoba prowadząca rozmowę kwalifikacyjną.

Algorytm

Dopasuj każdy początek do jego końca i dodaj [newStart, newEnd] do listy.
Posortuj przedziały według początku.
Przejdź przez nie w kolejności, przechowując ostatni scalony przedział.
Jeśli następny początek jest nie większy niż przechowywany koniec, ustaw przechowywany koniec na większy z tych dwóch końców.
W przeciwnym razie dodaj następny przedział jako nowy scalony przedział. Zwróć scaloną listę.

def insertInterval(starts, ends, newStart, newEnd):
    intervals = list(zip(starts, ends))
    intervals.append((newStart, newEnd))
    intervals.sort()
    merged = []
    for start, end in intervals:
        if merged and start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)  # overlaps or touches: stretch
        else:
            merged.append([start, end])  # a real gap: a new interval begins
    return merged

Jedno przejście w trzech częściach

Intuicja

Przejdź raz po liście, używając indeksu i, i podziel ją na trzy grupy. Najpierw każdy przedział, dla którego ends[i] < newStart, kończy się przed początkiem nowego, więc nie ma z nim żadnego punktu wspólnego: skopiuj go do wyniku. Warunek używa ścisłego <, ponieważ przedział kończący się dokładnie w newStart styka się z nowym przedziałem i trzeba je połączyć.

Po drugie, każdy przedział, dla którego starts[i] ≤ mergedEnd, pokrywa się z przedziałem, który tworzysz, lub styka się z nim. Włącz go do przedziału: mergedStart przyjmuje mniejszy początek, a mergedEnd — większy koniec. Przedziały w tej grupie leżą obok siebie, ponieważ lista jest posortowana. Gdy tylko jakiś przedział zaczyna się po mergedEnd, każdy następny zaczyna się jeszcze dalej, więc żaden z nich nie może już zostać połączony. Dodaj połączony przedział; ten krok obsługuje też przypadek, gdy grupa jest pusta i nowy przedział trafia do wyniku samodzielnie.

Po trzecie, skopiuj wszystko, co zostało. Te przedziały zaczynają się po końcu połączonego przedziału, a między sobą już wcześniej były rozdzielone.

Prześledźmy pierwszy przykład. [1, 3] kończy się przed 6: skopiuj go. [5, 7] zaczyna się w 5, czyli nie później niż 11: połączony przedział zmienia się na [5, 11]. [10, 12] zaczyna się w 10, czyli nie później niż 11: zmienia się na [5, 12]. [15, 18] zaczyna się po 12, więc dodaj [5, 12] i skopiuj [15, 18]. Każdy przedział jest sprawdzany raz, więc złożoność czasowa wynosi O(n), a jedyną dodatkową pamięcią jest sam wynik.

Algorytm

Kopiuj przedziały do wyniku, dopóki ends[i] < newStart.
Ustaw mergedStart = newStart i mergedEnd = newEnd.
Dopóki starts[i] ≤ mergedEnd, ustaw mergedStart na mniejszy początek, a mergedEnd na większy koniec, i przejdź dalej.
Dodaj [mergedStart, mergedEnd].
Skopiuj pozostałe przedziały i zwróć wynik.

def insertInterval(starts, ends, newStart, newEnd):
    n = len(starts)
    result = []
    i = 0
    # 1. Intervals that end before the new one starts stay as they are.
    while i < n and ends[i] < newStart:
        result.append([starts[i], ends[i]])
        i += 1
    # 2. Intervals that overlap or touch the new one fold into it.
    mergedStart, mergedEnd = newStart, newEnd
    while i < n and starts[i] <= mergedEnd:
        mergedStart = min(mergedStart, starts[i])
        mergedEnd = max(mergedEnd, ends[i])
        i += 1
    result.append([mergedStart, mergedEnd])
    # 3. Intervals that start after the merged one ends stay as they are.
    while i < n:
        result.append([starts[i], ends[i]])
        i += 1
    return result

Pułapki i przypadki brzegowe

Pętla jest krótka, więc większość błędów wynika z jednego nieprawidłowego porównania albo pominięcia przypadku na początku lub końcu listy.

Użycie niewłaściwej nierówności dla stykających się przedziałów. Przy ends[i] ≤ newStart w pierwszej pętli lub starts[i] < mergedEnd w drugiej przedziały [2, 4] i [4, 8] pozostają rozdzielone. Stykające się przedziały są scalane, więc pierwszy warunek jest ostry, a drugi nie.
Scalanie przedziałów, które tylko wyglądają na sąsiadujące. [1, 2] i [3, 4] nie mają wspólnych punktów, więc porównanie z mergedEnd + 1 łączy przedziały, które powinny pozostać rozdzielone.
Pozostawienie newStart jako początku scalonego przedziału. Gdy nowy przedział zaczyna się wewnątrz starego, jak [6, 11] wewnątrz [5, 7], wynik zaczyna się od 5. Wybierz mniejszą z dwóch wartości początkowych.
Dodawanie nowego przedziału tylko wtedy, gdy pokrywa się z którymś z istniejących. Gdy znajduje się przed wszystkimi przedziałami, za nimi lub w przerwie między nimi, środkowa pętla się nie wykonuje, a nowy przedział i tak trzeba dodać.
Odczytywanie starts[i] lub ends[i] przed sprawdzeniem i < n. Gdy nowy przedział wykracza poza ostatni przedział, indeks wychodzi poza koniec tablic.

Najczęstsze pytania4

Jaka jest złożoność czasowa wstawiania przedziału?

Rozwiązanie jednoprzejściowe działa w czasie O(n): każdy przedział jest kopiowany lub scalany dokładnie raz. Wynik zawiera maksymalnie n+1 przedziałów, więc zajmuje O(n) pamięci, a nic innego nie zwiększa się wraz z rozmiarem danych wejściowych. Dodanie przedziału i ponowne sortowanie zajmuje natomiast O(n log n).

Czym Insert Interval różni się od Merge Intervals?

Merge Intervals zaczyna się od nieposortowanej listy, w której dowolny przedział może nakładać się na inny, dlatego najpierw trzeba ją posortować. W Insert Interval lista jest już posortowana, a stare przedziały nigdy się nie stykają, więc tylko nowy przedział może spowodować scalenie. Przedziały, z którymi się scala, tworzą jeden nieprzerwany ciąg, dlatego wystarczy jedno przejście bez sortowania.

Jak sprawdzić, czy dwa przedziały nakładają się na siebie?

Przedziały [a, b] i [c, d] mają co najmniej jeden wspólny punkt dokładnie wtedy, gdy a ≤ d i c ≤ b. Oznacza to, że stykające się przedziały, takie jak [2, 4] i [4, 8], są uznawane za nakładające się, czego wymaga to zadanie. Jeśli stykające się przedziały miałyby pozostać rozłączne, zamiast tego użyłbyś a < d i c < b.

Czy wyszukiwanie binarne może przyspieszyć wstawianie przedziału?

Wyszukiwanie binarne znajduje początek i koniec połączonego ciągu w czasie O(log n), ponieważ zarówno początki, jak i końce są posortowane. Funkcja nadal jednak zwraca nową listę, a skopiowanie do niej niezmienionych przedziałów kosztuje O(n). Całość pozostaje więc w O(n). Wyszukiwanie binarne się opłaca, gdy przedziały znajdują się w strukturze, która może usuwać i wstawiać zakres bez kopiowania, takiej jak zrównoważone drzewo.

Python

def insertInterval(starts, ends, newStart, newEnd):
    # Wpisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

starts = [1, 5, 10, 15]
ends = [3, 7, 12, 18]
newStart = 6
newEnd = 11

Oczekiwane

[[1, 3], [5, 12], [15, 18]]