Non-overlapping Intervals

+10

Otrzymujesz listę przedziałów w postaci dwóch tablic: przedział i rozciąga się od starts[i] do ends[i]. Usuń jak najmniej przedziałów, aby żadne dwa z pozostałych się nie nakładały. Dwa przedziały, które tylko się stykają — gdy jeden kończy się dokładnie w punkcie, w którym zaczyna się drugi — nie nakładają się.

Napisz funkcję o nazwie eraseOverlapIntervals, która zwraca najmniejszą liczbę przedziałów, które trzeba usunąć.

Funkcja

eraseOverlapIntervals(starts: integer-array, ends: integer-array) → integer

startsinteger-array: początek każdego przedziału
endsinteger-array: koniec każdego przedziału, pod tym samym indeksem co jego początek
Zwracainteger: jak najmniej przedziałów do usunięcia, aby pozostałe na siebie nie nachodziły

Ograniczenia

1 ≤ starts.length == ends.length ≤ 5000
-5 × 10⁴ ≤ starts[i] < ends[i] ≤ 5 × 10⁴
Przedziały nie są posortowane. Dwa przedziały mogą być identyczne.

Przykłady

Wejście: starts = [3, 1, 5, 2]ends = [6, 4, 7, 3]
Wyjście: 2
Wyjaśnienie: W kolejności początków przedziały to [1,4], [2,3], [3,6] i [5,7]. Zostaw [2,3] i [3,6], które tylko się stykają, a pozostałe 2 usuń. Nie możesz zostawić trzech: [1,4] nakłada się na [2,3], a [3,6] nakłada się na [5,7]; każda trójka spośród tych czterech zawiera jedną z tych par.

Wejście: starts = [0, 0, 0]ends = [5, 5, 5]
Wyjście: 2
Wyjaśnienie: Wszystkie trzy przedziały to [0,5], więc dowolne dwa z nich się nakładają. Może pozostać tylko jeden, a pozostałe 2 usuwasz.

Wejście: starts = [4, 1, 2]ends = [6, 2, 4]
Wyjście: 0
Wyjaśnienie: [1,2], [2,4] i [4,6] stykają się końcem z początkiem i nigdy się nie nakładają, więc niczego nie usuwasz, a odpowiedź to 0.

+17 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Załóżmy, że każdy przedział ma również wartość, a Ty chcesz uzyskać jak największą łączną wartość spośród niepokrywających się przedziałów. Czy wybór przedziału, który kończy się najwcześniej, nadal się sprawdzi? Czego użyjesz zamiast tego?

Rozwiązanie

Usunięcie jak najmniejszej liczby przedziałów jest równoznaczne z zachowaniem jak największej liczby przedziałów, które na siebie nie nachodzą, więc odpowiedzią jest n minus liczba elementów w tym największym zbiorze. Sprawdzenie każdego zestawu, który można zachować, wymaga czasu wykładniczego, a programowanie dynamiczne dla łańcuchów przedziałów obniża złożoność do O(n²). Jedna zachłanna reguła kończy zadanie w czasie O(n log n): spośród przedziałów, które nadal pasują, zawsze zachowuj ten, który kończy się najwcześniej.

Zachowaj lub usuń każdy przedział

Poprawne, ale nie kończy się na największych testach

Intuicja

Odwróć pytanie. Usunięcie jak najmniejszej liczby przedziałów oznacza zachowanie jak największej liczby przedziałów, które na siebie nie zachodzą, a odpowiedź to n minus ta liczba. Szukaj więc największego zbioru, jaki możesz zachować.

Posortuj przedziały według początku i dla każdego z nich zdecyduj, w tej kolejności, czy go usunąć, czy zachować. Możesz go zachować tylko wtedy, gdy zaczyna się w chwili równej końcowi ostatniego zachowanego przedziału lub później. Ten jeden warunek wystarczy: zachowane przedziały tworzą wtedy łańcuch, w którym każdy zaczyna się w chwili równej końcowi poprzedniego przedziału lub później, więc żadne dwa na siebie nie zachodzą. Przy każdym przedziale wypróbuj obie możliwości i wybierz lepszy wynik.

W pierwszym przykładzie posortowane przedziały to [1,4], [2,3], [3,6], [5,7]. Zachowanie [1,4] blokuje [2,3] i [3,6], które zaczynają się przed 4, ale pozostawia miejsce na [5,7]: zachowane są 2. Usunięcie [1,4] i zachowanie [2,3], a następnie [3,6], również pozwala zachować 2. Żadna gałąź nie osiąga 3, więc usuwasz 4-2 = 2.

Każdy przedział może podwoić liczbę gałęzi, więc n przedziałów prowadzi do maksymalnie 2^n ścieżek. Już trzydzieści przedziałów, które na siebie nie zachodzą, oznacza ponad miliard wywołań, a testy obejmują do 5000 przedziałów. Rekurencja sięga też n poziomów w głąb: 5000 wywołań w największych testach, czyli więcej niż domyślny limit Pythona wynoszący 1,000.

Algorytm

Posortuj przedziały według początku, zachowując każdy początek razem z jego końcem.
Zdefiniuj mostKept(i, last): największą liczbę przedziałów, które możesz zachować od pozycji i, gdy last jest pozycją ostatniego zachowanego przedziału (-1, jeśli nie ma żadnego).
Poza końcem listy zwróć 0. W przeciwnym razie zacznij od mostKept(i+1, last), czyli wyniku usunięcia przedziału i.
Jeśli początek przedziału i przypada w chwili końca przedziału last lub później, wypróbuj również 1 + mostKept(i+1, i) i zachowaj większy wynik.
Zwróć n minus mostKept(0, -1).

def eraseOverlapIntervals(starts, ends):
    intervals = sorted(zip(starts, ends))  # by start time
    n = len(intervals)

    def most_kept(i, last):
        # The most intervals you can keep among i..n-1, when interval last
        # is the latest one kept so far (-1: nothing kept yet).
        if i == n:
            return 0
        best = most_kept(i + 1, last)  # remove interval i
        if last == -1 or intervals[i][0] >= intervals[last][1]:
            best = max(best, 1 + most_kept(i + 1, i))  # keep interval i
        return best

    return n - most_kept(0, -1)

Najdłuższy łańcuch z wykorzystaniem programowania dynamicznego

Poprawne, ale nie kończy się na największych testach

Intuicja

Wyszukiwanie opisane powyżej wciąż odpowiada na to samo pytanie: jaki jest najdłuższy łańcuch kończący się tym przedziałem? Zapisz tę odpowiedź raz dla każdego przedziału. Posortuj przedziały według początku i niech chain[i] oznacza maksymalną liczbę przedziałów, które możesz zachować, gdy przedział i jest ostatnim zachowanym.

Przedział zachowany bezpośrednio przed i musi kończyć się w starts[i] lub wcześniej. Każdy taki przedział występuje wcześniej w kolejności sortowania: zaczyna się przed swoim końcem, więc zaczyna się przed starts[i]. Stąd chain[i] = 1 + chain[j] dla najlepszego wcześniejszego j, dla którego ends[j] ≤ starts[i], albo 1, jeśli żaden przedział nie pasuje. Największa wartość w chain to maksymalna liczba przedziałów, które możesz zachować.

W pierwszym przykładzie, po posortowaniu: [1,4], [2,3], [3,6], [5,7], wartości wynoszą 1, 1, 2 i 2: [3,6] może następować po [2,3], a [5,7] może następować po [1,4] lub [2,3]. Najdłuższy łańcuch ma długość 2, więc usuwasz 4-2 = 2.

Każdy przedział sprawdza wszystkie przedziały, które go poprzedzają, co daje n(n-1)/2 sprawdzeń. Dla n = 5000 to około 12,5 miliona sprawdzeń: akceptowalnie w języku kompilowanym, zbyt wolno w wolniejszych językach dla największych testów i znacznie gorzej niż poniższe podejście zachłanne.

Algorytm

Posortuj przedziały według początku, zachowując każdy początek razem z jego końcem.
Ustaw chain[i] = 1 dla każdego przedziału.
Dla każdego i i każdego j < i, dla którego ends[j] ≤ starts[i], ustaw chain[i] na chain[j]+1, jeśli ta wartość jest większa.
Zwróć n pomniejszone o największą wartość w chain.

def eraseOverlapIntervals(starts, ends):
    intervals = sorted(zip(starts, ends))  # by start time
    n = len(intervals)
    # chain[i]: the most intervals you can keep when interval i is the last one kept
    chain = [1] * n
    for i in range(n):
        for j in range(i):
            if intervals[j][1] <= intervals[i][0] and chain[j] + 1 > chain[i]:
                chain[i] = chain[j] + 1
    return n - max(chain)

Algorytm zachłanny: zachowaj przedział, który kończy się najwcześniej

Intuicja

Spójrz na przedział o najmniejszym końcu. Każde optymalne rozwiązanie zawsze go zachowuje. Weź dowolny największy zbiór przedziałów, które możesz zachować, i zamień jego najwcześniejszy przedział na ten. Nowy przedział kończy się nie później niż przedział, który zastąpił, więc nadal kończy się w chwili równej początkowi następnego zachowanego przedziału lub wcześniej. Zbiór nadal nie zawiera nakładających się przedziałów i zachowuje swój rozmiar, więc zachowanie przedziału o najwcześniejszym końcu nic cię nie kosztuje.

Gdy go zachowasz, każdy przedział, który zaczyna się przed jego końcem, nakłada się na niego i musi zostać usunięty. Pozostałe przedziały tworzą to samo zadanie dla przedziałów, które zaczynają się w chwili równej temu końcowi lub później, więc zastosuj tę samą regułę ponownie. W praktyce: posortuj przedziały według końca, przejdź po liście i zapamiętuj lastEnd, czyli koniec ostatniego zachowanego przedziału. Zachowaj przedział, który zaczyna się w chwili równej lastEnd lub później; każdy inny przedział zalicz do usuniętych.

Pierwszy przykład po posortowaniu według końca wygląda tak: [2,3], [1,4], [3,6], [5,7]. Zachowaj [2,3], więc lastEnd = 3. [1,4] zaczyna się w chwili 1, przed 3: usuń go. [3,6] zaczyna się w chwili 3, nie przed 3: zachowaj go, lastEnd = 6. [5,7] zaczyna się w chwili 5, przed 6: usuń go. Usunięte zostały dwa przedziały.

Inne kryteria sortowania wydają się kuszące, ale zawodzą. Sortowanie według początku zachowuje [0,100], gdy pokrywa ono [1,2], [3,4] i [5,6], i usuwa trzy przedziały zamiast jednego. Zachowywanie najkrótszego przedziału zawodzi dla [1,5], [4,7], [6,10]: krótki [4,7] nakłada się na oba pozostałe, więc jego zachowanie kosztuje usunięcie dwóch przedziałów, podczas gdy wystarczy usunąć jeden. To koniec przedziału pozwala zostawić najwięcej miejsca na wszystko, co następuje po nim.

Sortowanie kosztuje O(n log n), a przejście po liście O(n). Posortowana kopia przedziałów zajmuje O(n) miejsca.

Algorytm

Posortuj przedziały według końca, zachowując przyporządkowanie każdego końca do jego początku.
Zachowaj pierwszy przedział: ustaw lastEnd na jego koniec, a removed na 0.
Dla każdego kolejnego przedziału, jeśli zaczyna się w punkcie lastEnd lub później, zachowaj go i ustaw lastEnd na jego koniec.
W przeciwnym razie zwiększ removed o 1.
Zwróć removed.

def eraseOverlapIntervals(starts, ends):
    intervals = sorted(zip(ends, starts))  # by end time
    removed = 0
    last_end = intervals[0][0]  # the interval that ends first is always kept
    for end, start in intervals[1:]:
        if start >= last_end:
            last_end = end  # it fits after the last kept interval: keep it
        else:
            removed += 1  # it overlaps the last kept interval: remove it
    return removed

Pułapki i przypadki brzegowe

Większość błędnych odpowiedzi wynika z klucza sortowania lub porównania w punkcie styku.

Uznawanie stykających się przedziałów za nakładające się. Przy użyciu start > lastEnd zamiast start ≥ lastEnd łańcuch [1,2], [2,4], [4,6] traci [2,4], który zaczyna się dokładnie tam, gdzie kończy się [1,2], więc wynikiem jest 1 zamiast 0.
Sortowanie według początku i zawsze zachowywanie wcześniejszego przedziału w przypadku nakładania się. Szeroki przedział [0,100] wypiera wtedy [1,2], [3,4] i [5,6]. Jeśli sortujesz według początku, spośród dwóch nakładających się przedziałów zachowaj ten, który kończy się wcześniej.
Porównywanie każdego przedziału z sąsiednim na posortowanej liście zamiast z ostatnim zachowanym przedziałem. Po usunięciu [1,4] następny przedział trzeba porównać z końcem [2,3], a nie z 4.
Sortowanie starts i ends jako dwóch osobnych list. Każdy koniec musi pozostać przypisany do swojego początku, w przeciwnym razie porównasz początek z końcem innego przedziału.
Zwracanie liczby zachowanych przedziałów. Pytanie dotyczy liczby usuniętych przedziałów, czyli n minus ta liczba.

Najczęstsze pytania4

Jaka jest złożoność czasowa problemu przedziałów niepokrywających się?

Rozwiązanie zachłanne sortuje przedziały według końca w czasie O(n log n), a następnie przechodzi przez nie raz w czasie O(n), więc łączna złożoność wynosi O(n log n). Posortowana kopia przedziałów zajmuje O(n) pamięci. Wersja z programowaniem dynamicznym ma złożoność O(n²), a sprawdzanie każdego zestawu, który można zachować, ma złożoność O(2^n).

Dlaczego sortowanie według czasu zakończenia pozwala usunąć najmniej przedziałów?

Przedział, który kończy się jako pierwszy, może zastąpić pierwszy przedział dowolnego optymalnego rozwiązania bez tworzenia nakładania się, ponieważ kończy się nie później. Zatem pewne optymalne rozwiązanie go zachowuje, a po usunięciu wszystkiego, co się z nim nakłada, pozostała część jest tym samym problemem dla mniejszego zbioru. Powtarzanie tego argumentu pokazuje, że każdy zachłanny wybór jest bezpieczny.

Czy możesz zamiast tego posortować według czasu rozpoczęcia?

Tak, przy innej zasadzie dotyczącej nakładania się przedziałów. Przejdź przez przedziały według początku i gdy następny nakłada się na ostatni zachowany przedział, policz jedno usunięcie i zachowaj ten z dwóch przedziałów, który kończy się wcześniej. Usuwa tę samą liczbę przedziałów co sortowanie według końca i działa w tym samym czasie O(n log n).

Czy problem przedziałów, które się nie nakładają, jest tym samym co problem wyboru aktywności?

To druga strona tego samego problemu. Wybór aktywności polega na znalezieniu jak największej liczby niepokrywających się przedziałów; w tym problemie trzeba usunąć ich jak najmniej, czyli n minus tę liczbę. Oba problemy rozwiązuje ta sama zachłanna reguła: zachowaj aktywność, która kończy się najwcześniej.

Python

def eraseOverlapIntervals(starts, ends):
    # Napisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

starts = [3, 1, 5, 2]
ends = [6, 4, 7, 3]

Oczekiwane

Non-overlapping Intervals

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Zachowaj lub usuń każdy przedział

Najdłuższy łańcuch z wykorzystaniem programowania dynamicznego

Algorytm zachłanny: zachowaj przedział, który kończy się najwcześniej

Pułapki i przypadki brzegowe

Najczęstsze pytania4

Podobne zadania