Non-overlapping Intervals

Q: Wie hoch ist die Zeitkomplexität von nicht überlappenden Intervallen?

Die Greedy-Lösung sortiert nach Endzeit in O(n log n) und durchläuft die Intervalle einmal, sodass die Gesamtlaufzeit O(n log n) beträgt und für die sortierte Kopie O(n) Speicher benötigt wird. Die dynamische Programmierlösung hat eine Laufzeit von O(n²) , und alle möglichen Teilmengen auszuprobieren, die beibehalten werden sollen, hat eine Laufzeit von O(2^n) .

MittelIntervalle Greedy

+10

Das Intervall i reicht von starts[i] bis ends[i]. Gib die kleinste Anzahl von Intervallen zurück, die du entfernen musst, damit sich keine zwei der übrigen überlappen. Zwei Intervalle, die sich nur berühren, wobei das eine genau an dem Punkt endet, an dem das andere beginnt, überlappen sich nicht.

Funktion

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

startsinteger-array: der Anfang jedes Intervalls
endsinteger-array: das Ende jedes Intervalls, am selben Index wie dessen Anfang
Gibt zurückinteger: die geringste Anzahl an Intervallen, die entfernt werden müssen, damit sich die übrigen nicht überschneiden

Einschränkungen

1 ≤ starts.length == ends.length ≤ 5000
-5 × 10⁴ ≤ starts[i] < ends[i] ≤ 5 × 10⁴
Die Intervalle sind nicht sortiert. Zwei Intervalle können identisch sein.

Beispiele

Eingabe: starts = [3, 1, 5, 2]ends = [6, 4, 7, 3]
Ausgabe: 2
Erklärung: In der Startreihenfolge lauten die Intervalle [1,4], [2,3], [3,6] und [5,7]. Behalte [2,3] und [3,6], die sich nur berühren, und entferne die anderen 2. Drei können nicht bleiben: [1,4] überschneidet sich mit [2,3], und [3,6] überschneidet sich mit [5,7].

Eingabe: starts = [0, 0, 0]ends = [5, 5, 5]
Ausgabe: 2
Erklärung: Alle drei Intervalle sind [0,5], daher überschneiden sich jeweils zwei. Eines bleibt, und du entfernst 2.

Eingabe: starts = [4, 1, 2]ends = [6, 2, 4]
Ausgabe: 0
Erklärung: [1,2], [2,4] und [4,6] schließen jeweils direkt aneinander an und überschneiden sich nie, daher entfernst du nichts und die Antwort ist 0.

Weiterführende Frage

Angenommen, jedes Intervall hat einen Wert und du möchtest den größten Gesamtwert unter den Intervallen ermitteln, die sich nicht überschneiden. Funktioniert es weiterhin, das Intervall zu behalten, das zuerst endet?

Lösung

Die möglichst wenigen Intervalle zu entfernen, ist gleichbedeutend damit, möglichst viele nicht überlappende Intervalle zu behalten: Die Antwort ist n minus dieser Anzahl. Eine Greedy-Regel ermittelt die Anzahl in O(n log n): Behalte unter den Intervallen, die noch hineinpassen, immer dasjenige, das zuerst endet.

Jedes Intervall behalten oder entfernen

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Sortiere die Intervalle nach ihrem Start und entscheide für jedes, ob du es behältst oder entfernst. Du darfst es nur behalten, wenn es am oder nach dem Ende des zuletzt behaltenen Intervalls beginnt, sodass die behaltenen Intervalle eine Kette ohne Überschneidungen bilden. Probiere bei jedem Intervall beide Möglichkeiten aus und nimm die größere Anzahl; die Antwort ist n minus diese Anzahl.

Jedes Intervall kann die Anzahl der Verzweigungen verdoppeln, sodass n Intervalle zu bis zu 2^n Pfaden führen. Dreißig Intervalle, die sich nicht überschneiden, bedeuten bereits über eine Milliarde Aufrufe, und n kann bis auf 5000 steigen.

Algorithmus

Sortiere die Intervalle nach ihrem Start und behalte jeden Start bei seinem jeweiligen Ende.
Definiere mostKept(i, last): die meisten Intervalle, die du ab Position i behalten kannst, wenn last das zuletzt behaltene Intervall ist (-1, wenn keines vorhanden ist).
Am Ende gibst du 0 zurück. Andernfalls nimmst du mostKept(i+1, last), wodurch Intervall i entfernt wird.
Wenn Intervall i am oder nach dem Ende von last beginnt, probiere außerdem 1 + mostKept(i+1, i) aus und behalte den größeren Wert.
Gib n minus mostKept(0, -1) zurück.

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)

Längste Kette mit dynamischer Programmierung

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Die Suche stellt immer wieder dieselbe Frage: Wie lang ist die längste Kette, die mit diesem Intervall endet? Beantworte sie einmal pro Intervall. Sortiere nach dem Start und sei chain[i] die größtmögliche Anzahl an Intervallen, die du behalten kannst, wenn Intervall i das letzte ist.

Ein Intervall, das direkt vor i kommen kann, endet bei oder vor starts[i], beginnt also früher und steht in der sortierten Reihenfolge davor. Daraus ergibt sich chain[i] = 1 + chain[j] für das beste passende j oder 1, falls keines passt. Im ersten Beispiel lauten die Werte 1, 1, 2 und 2, also behältst du 2 und entfernst 2.

Die doppelte Schleife führt n(n-1)/2 Prüfungen durch: bei n = 5000 etwa 12,5 Millionen.

Algorithmus

Sortiere die Intervalle nach ihrem Start und ordne jedem Start sein Ende zu.
Setze für jedes Intervall chain[i] = 1.
Setze für jedes i und jedes j < i mit ends[j] ≤ starts[i] chain[i] auf chain[j]+1, wenn dieser Wert größer ist.
Gib n minus den größten Wert in chain zurück.

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)

Greedy: Behalte das Intervall, das zuerst endet

Idee

Nimm das Intervall mit dem kleinsten Endpunkt. Eine optimale Lösung behält es bei: In jeder größtmöglichen Menge, die du behalten kannst, kannst du das früheste Intervall durch dieses ersetzen. Es endet nicht später, sodass es weiterhin endet, bevor oder genau dann, wenn das nächste beibehaltene Intervall beginnt, und die Menge behält ihre Größe ohne Überlappungen. Jedes Intervall, das vor seinem Ende beginnt, überlappt es und muss entfernt werden. Übrig bleibt dasselbe Problem mit den Intervallen, die an oder nach diesem Ende beginnen.

Im ersten Beispiel behältst du, nach Endpunkt sortiert, [2,3], entfernst [1,4], behältst [3,6] und entfernst [5,7]. Stattdessen das kürzeste Intervall zu behalten, scheitert bei [1,5], [4,7], [6,10]: [4,7] überlappt beide anderen und kostet zwei Entfernungen, obwohl eine ausreicht.

Das Sortieren kostet O(n log n) und das Durchlaufen O(n).

Algorithmus

Sortiere die Intervalle nach ihrem Ende und behalte jedes Ende bei seinem zugehörigen Anfang.
Behalte das erste Intervall: Setze lastEnd auf sein Ende und removed auf 0.
Für jedes folgende Intervall: Wenn es bei oder nach lastEnd beginnt, behalte es und setze lastEnd auf sein Ende.
Andernfalls erhöhe removed um 1.
Gib removed zurück.

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

Stolperfallen und Grenzfälle

Berührende Intervalle als überlappend behandeln. Mit start > lastEnd statt start ≥ lastEnd ergibt die Kette [1,2], [2,4], [4,6] den Wert 1 statt 0.
Nach dem Start sortieren und bei einer Überlappung das frühere Intervall behalten. Ein breites [0,100] verdrängt dann [1,2], [3,4] und [5,6]: drei Entfernungen statt einer.
Jedes Intervall mit seinem Nachbarn in der sortierten Liste vergleichen, statt mit dem zuletzt beibehaltenen Intervall. Im ersten Beispiel muss [3,6] mit dem Ende von [2,3] verglichen werden, nicht mit dem des entfernten [1,4], sonst ergibt sich als Antwort 3.
starts und ends als zwei separate Listen sortieren. Jedes Ende muss bei seinem eigenen Start bleiben.
Zurückgeben, wie viele Intervalle du behältst, statt wie viele du entfernst.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität von nicht überlappenden Intervallen?

Die Greedy-Lösung sortiert nach Endzeit in O(n log n) und durchläuft die Intervalle einmal, sodass die Gesamtlaufzeit O(n log n) beträgt und für die sortierte Kopie O(n) Speicher benötigt wird. Die dynamische Programmierlösung hat eine Laufzeit von O(n²), und alle möglichen Teilmengen auszuprobieren, die beibehalten werden sollen, hat eine Laufzeit von O(2^n).

Kannst du stattdessen nach der Startzeit sortieren?

Ja, mit einer anderen Regel für Überlappungen. Gehe die Intervalle nach ihrem Start durch. Wenn sich das nächste mit dem zuletzt beibehaltenen Intervall überschneidet, zähle eine Entfernung und behalte das Intervall, das früher endet. Das ergibt dieselbe Anzahl in derselben Zeit von O(n log n).

Ist das Problem der nicht überlappenden Intervalle dasselbe wie das Aktivitätsauswahlproblem?

Es ist die andere Seite derselben Sache. Bei der Aktivitätsauswahl wird nach der maximalen Anzahl von Intervallen gefragt, die sich nicht überschneiden; bei diesem Problem geht es darum, die wenigsten zu entfernen, also n minus dieser Anzahl. Dieselbe Greedy-Regel – die Aktivität behalten, die zuerst endet – löst beide Probleme.

def eraseOverlapIntervals(starts, ends):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argumente

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

Erwartete Ausgabe

Non-overlapping Intervals

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Jedes Intervall behalten oder entfernen

Längste Kette mit dynamischer Programmierung

Greedy: Behalte das Intervall, das zuerst endet

Stolperfallen und Grenzfälle

Häufige Fragen3

Ähnliche Aufgaben