Non-overlapping Intervals

+10

Przedział i rozciąga się od starts[i] do ends[i]. Zwróć najmniejszą liczbę przedziałów, które musisz usunąć, 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ę.

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: najmniejsza liczba przedziałów do usunięcia, aby pozostałe się nie nakładał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ątkowej 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 mogą zostać trzy: [1,4] nachodzi na [2,3], a [3,6] nachodzi na [5,7].

Wejście: starts = [0, 0, 0]ends = [5, 5, 5]
Wyjście: 2
Wyjaśnienie: Wszystkie trzy przedziały to [0,5], więc każde dwa się pokrywają. Jeden zostaje, a ty usuwasz 2.

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.

Pytanie dodatkowe

Załóżmy, że każdy przedział ma swoją 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ę sprawdza?

Rozwiązanie

Usunięcie jak najmniejszej liczby przedziałów jest tym samym co zachowanie jak największej liczby przedziałów, które się nie nakładają: odpowiedź to n minus ta liczba. Jedna zachłanna reguła pozwala znaleźć tę liczbę 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

Posortuj przedziały według początku i zdecyduj dla każdego z nich, czy go zachować, czy usunąć. Możesz go zachować tylko wtedy, gdy zaczyna się w chwili równej lub późniejszej niż koniec ostatniego zachowanego przedziału, dzięki czemu zachowane przedziały tworzą łańcuch bez nakładania się. Wypróbuj obie możliwości dla każdego przedziału i wybierz większą liczbę; odpowiedź to n minus ta liczba.

Każdy przedział może podwoić liczbę gałęzi, więc n przedziałów prowadzi do nawet 2^n ścieżek. Już trzydzieści nienakładających się przedziałów oznacza ponad miliard wywołań, a n może wynosić nawet 5000.

Algorytm

Posortuj przedziały według początku, zachowując przyporządkowanie każdego początku do jego końca.
Zdefiniuj mostKept(i, last): maksymalną liczbę przedziałów, które można zachować od pozycji i, gdy last jest ostatnim zachowanym przedziałem (-1, jeśli nie ma żadnego).
Poza końcem zwróć 0. W przeciwnym razie przyjmij mostKept(i+1, last), co usuwa przedział i.
Jeśli przedział i zaczyna się na końcu przedziału last lub później, wypróbuj też 1 + mostKept(i+1, i) i zachowaj większą wartość.
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 programowaniem dynamicznym

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

Intuicja

Wyszukiwanie wciąż zadaje to samo pytanie: jak długi jest najdłuższy łańcuch kończący się tym przedziałem? Odpowiedz na nie raz dla każdego przedziału. Posortuj przedziały według początku i niech chain[i] oznacza największą liczbę przedziałów, które możesz zachować, jeśli ostatnim jest przedział i.

Przedział, który może wystąpić bezpośrednio przed i, kończy się w chwili starts[i] lub wcześniej, więc zaczyna się wcześniej i znajduje się wcześniej w posortowanej kolejności. Otrzymujemy chain[i] = 1 + chain[j] dla najlepszego takiego j albo 1, jeśli żaden nie pasuje. W pierwszym przykładzie wartości wynoszą 1, 1, 2 i 2, więc zachowujesz 2 i usuwasz 2.

Podwójna pętla wykonuje n(n-1)/2 sprawdzeń: około 12.5 miliona dla n = 5000.

Algorytm

Posortuj przedziały według początku, zachowując powiązanie każdego początku 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

Wybierz przedział, który kończy się najwcześniej. Istnieje optymalne rozwiązanie, które go zachowuje: w dowolnym największym zbiorze, który możesz zachować, zamień najwcześniejszy przedział na ten. Kończy się nie później, więc nadal kończy się w chwili rozpoczęcia kolejnego zachowanego przedziału lub wcześniej, a zbiór zachowuje swój rozmiar i nie zawiera nakładających się przedziałów. Każdy przedział, który zaczyna się przed jego końcem, nakłada się na niego i musi zostać usunięty. Pozostaje ten sam problem dotyczący przedziałów, które zaczynają się w chwili jego końca lub później.

W pierwszym przykładzie, po posortowaniu według końca, zachowujesz [2,3], usuwasz [1,4], zachowujesz [3,6] i usuwasz [5,7]. Zamiast tego zachowanie najkrótszego przedziału nie działa w przypadku [1,5], [4,7], [6,10]: [4,7] nakłada się na oba pozostałe, więc trzeba usunąć dwa przedziały, choć wystarczy jeden.

Sortowanie kosztuje O(n log n), a przejście przez przedziały O(n).

Algorytm

Posortuj przedziały według końca, zachowując każdy koniec razem z jego początkiem.
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

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] daje wynik 1 zamiast 0.
Sortowanie według początku i pozostawianie wcześniejszego przedziału przy nakładaniu się. Szeroki przedział [0,100] wypiera wtedy [1,2], [3,4] i [5,6]: trzy usunięcia zamiast jednego.
Porównywanie każdego przedziału z sąsiednim na posortowanej liście zamiast z ostatnim zachowanym przedziałem. W pierwszym przykładzie [3,6] trzeba porównać z końcem [2,3], a nie usuniętego [1,4], inaczej wynikiem będzie 3.
Sortowanie starts i ends jako dwóch osobnych list. Każdy koniec musi pozostać przypisany do własnego początku.
Zwracanie liczby zachowanych przedziałów zamiast liczby usuniętych.

Najczęstsze pytania3

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

Rozwiązanie zachłanne sortuje przedziały według końca w czasie O(n log n) i przechodzi przez nie jeden raz, więc łączna złożoność wynosi O(n log n), a pamięć potrzebna na posortowaną kopię to O(n). Wersja z programowaniem dynamicznym ma złożoność O(n²), a sprawdzenie każdego zbioru, który można zachować, ma złożoność O(2^n).

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

Tak, przy innej regule dotyczącej nakładania się przedziałów. Przejdź przez przedziały w kolejności według początku, a gdy kolejny nakłada się na ostatni zachowany przedział, policz jedno usunięcie i zachowaj ten z dwóch, który kończy się wcześniej. Daje to ten sam wynik w tym samym czasie O(n log n).

Czy problem przedziałów niepokrywających się to to samo co problem wyboru aktywności?

To druga strona tego problemu. Wybór aktywności polega na znalezieniu jak największej liczby przedziałów, które się nie nakładają; w tym problemie trzeba usunąć jak najmniej przedziałów, czyli n minus tę liczbę. Ta sama zachłanna zasada — zachowaj aktywność, która kończy się najwcześniej — rozwiązuje oba problemy.

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

Test #1

Test #2

Test #3

Argumenty

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

Oczekiwany wynik

Non-overlapping Intervals

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Zachowaj lub usuń każdy przedział

Najdłuższy łańcuch z programowaniem dynamicznym

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

Pułapki i przypadki brzegowe

Najczęstsze pytania3

Podobne zadania