Insert Interval

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

Rozwiązanie jednokrotnego przejścia działa w czasie O(n) , ponieważ każdy przedział jest kopiowany lub scalany tylko raz, i wykorzystuje O(n) pamięci na wynik zawierający maksymalnie n+1 przedziałów. Dodanie przedziału i ponowne sortowanie zajmuje O(n log n) .

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

Scalanie przedziałów zaczyna się od nieposortowanej listy, w której dowolny przedział może nachodzić na dowolny inny, więc najpierw ją sortuje. Tutaj lista jest posortowana, a stare przedziały nigdy się nie stykają, więc tylko nowy przedział może wywołać scalanie, a przedziały, z którymi się scala, tworzą jeden ciąg. Wystarczy jedno przejście.

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

[a, b] i [c, d] mają punkt wspólny 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ę, zgodnie z założeniem tego zadania. Aby stykające się przedziały traktować jako rozłączne, użyj a < d i c < b .

ŚredniePrzedziały

+10

Otrzymujesz przedziały posortowane według początku jako dwie tablice: przedział i to [starts[i], ends[i]], a żadne dwa przedziały się nie nakładają ani nie stykają. Wstaw nowy przedział [newStart, newEnd], połącz go z każdym przedziałem, z którym się nakłada lub styka, i zwróć wszystkie przedziały jako pary [start, end] posortowane według początku.

Przedziały stykają się, gdy koniec jednego wypada tam, gdzie zaczyna się drugi, jak w przypadku [2, 4] i [4, 8], a stykające się przedziały są łączone. [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ątki 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 start

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 stają się [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 i z [8, 9] w punkcie 8, 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 luce między 2 a 9 i nie styka się z żadnym z sąsiadów, więc wstawia się między nimi i nic się nie scala.

Pytanie dodatkowe

Jeśli wstawisz wiele przedziałów jeden po drugim, jak je przechowywać, aby każde wstawienie kosztowało O(log n) plus jeden krok na każdy stary przedział, który pochłonie?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Stare przedziały są posortowane i rozłączne, więc tylko nowy przedział może spowodować scalenie. Dzieli to listę na trzy ciągi: przedziały, które kończą się przed jego początkiem, przedziały, które nakładają się na niego lub go dotykają, oraz przedziały, które zaczynają się po jego końcu. Skopiuj pierwszy ciąg, połącz środkowy w jeden przedział, skopiuj ostatni. Jedno przejście, bez sortowania.

Dodaj to i ponownie scal wszystko

Intuicja

Ponowne użycie scalania przedziałów: dodaj nowy przedział, posortuj wszystkie n+1 przedziały według początku i przejdź przez nie, trzymając ostatni scalony przedział. Po sortowaniu przedział może nakładać się tylko na grupę bezpośrednio przed nim, więc jeśli kolejny początek znajduje się na końcu trzymanego przedziału lub przed nim, przesuń koniec; w przeciwnym razie powstaje przerwa i zaczyna się nowy przedział.

Sortowanie kosztuje O(n log n) i naprawia listę, która jest nieuporządkowana w jednym miejscu, a przy tym pomija fakt, że stare przedziały nigdy nie łączą się ze sobą.

Algorytm

Połącz każdy początek z jego końcem 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ększą z tych dwóch wartości.
W przeciwnym razie dołącz 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

Lista jest posortowana, a jej przedziały są rozłączne, więc przedziały, które stykają się z nowym przedziałem, tworzą jeden nieprzerwany ciąg. Wszystko przed tym ciągiem spełnia warunek ends[i] < newStart: kończy się przed początkiem nowego przedziału. Warunek jest ścisły, ponieważ przedział, który kończy się dokładnie w newStart, styka się z nowym przedziałem i trzeba je scalić.

W tym ciągu przedział, dla którego starts[i] ≤ mergedEnd, nakłada się na przedział, który tworzysz, lub styka się z nim, więc rozszerza go do mniejszego początku i większego końca. Pierwszy przedział, który zaczyna się po mergedEnd, kończy ten ciąg, ponieważ każdy następny zaczyna się dalej na prawo. Gdy ciąg jest pusty, nowy przedział zostaje dodany samodzielnie. W pierwszym przykładzie przedział [1, 3] jest kopiowany, przedziały [5, 7] i [10, 12] rozszerzają [6, 11] do [5, 12], a [15, 18] jest kopiowany. Każdy przedział jest sprawdzany raz: czas O(n) i brak dodatkowej pamięci poza wynikiem.

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

Nieprawidłowe nierówności dla stykających się przedziałów. Gdy w pierwszej pętli użyjesz ends[i] ≤ newStart albo w drugiej starts[i] < mergedEnd, [2, 4] i [4, 8] pozostaną rozdzielone. Pierwszy test jest ścisły, drugi nie.
Porównywanie z mergedEnd + 1. Spowoduje to połączenie [1, 2] i [3, 4], które nie mają wspólnego punktu.
Pozostawienie newStart jako początku scalonego przedziału. [6, 11] zaczyna się wewnątrz [5, 7], więc wynik zaczyna się od 5.
Dodawanie nowego przedziału tylko wtedy, gdy nakłada się na inny. Gdy znajdzie się w luce lub poza jednym z końców, jak [5, 6], środkowa pętla się nie wykona, ale przedział i tak trzeba dodać.
Odczytywanie starts[i] przed sprawdzeniem i < n. Nowy przedział, który sięga poza ostatni, spowoduje wyjście indeksu poza zakres.

Najczęstsze pytania3

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

Rozwiązanie jednokrotnego przejścia działa w czasie O(n), ponieważ każdy przedział jest kopiowany lub scalany tylko raz, i wykorzystuje O(n) pamięci na wynik zawierający maksymalnie n+1 przedziałów. Dodanie przedziału i ponowne sortowanie zajmuje O(n log n).

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

Scalanie przedziałów zaczyna się od nieposortowanej listy, w której dowolny przedział może nachodzić na dowolny inny, więc najpierw ją sortuje. Tutaj lista jest posortowana, a stare przedziały nigdy się nie stykają, więc tylko nowy przedział może wywołać scalanie, a przedziały, z którymi się scala, tworzą jeden ciąg. Wystarczy jedno przejście.

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

[a, b] i [c, d] mają punkt wspólny 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ę, zgodnie z założeniem tego zadania. Aby stykające się przedziały traktować jako rozłączne, użyj a < d i c < b.

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

Test #1

Test #2

Test #3

Argumenty

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

Oczekiwany wynik

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