Non-overlapping Intervals

+10

Du erhältst eine Liste von Intervallen als zwei Arrays: Das Intervall i reicht von starts[i] bis ends[i]. Entferne so wenige Intervalle wie möglich, sodass sich keine zwei der verbleibenden Intervalle überschneiden. Zwei Intervalle, die sich nur berühren, bei denen also eines genau an dem Punkt endet, an dem das andere beginnt, überschneiden sich nicht.

Schreibe eine Funktion namens eraseOverlapIntervals, die die kleinste Anzahl von Intervallen zurückgibt, die du entfernen musst.

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 sein Anfang
Gibt zurückinteger: die geringstmögliche 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 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. Du kannst nicht drei behalten: [1,4] überschneidet sich mit [2,3] und [3,6] überschneidet sich mit [5,7], und beliebige drei der vier enthalten eines dieser Paare.

Eingabe: starts = [0, 0, 0]ends = [5, 5, 5]
Ausgabe: 2
Erklärung: Die drei Intervalle sind alle [0,5], daher überschneiden sich jeweils zwei von ihnen. Nur eines kann bleiben, und die anderen 2 entfernst du.

Eingabe: starts = [4, 1, 2]ends = [6, 2, 4]
Ausgabe: 0
Erklärung: [1,2], [2,4] und [4,6] treffen jeweils am Ende auf den Anfang und überlappen sich nie, daher entfernst du nichts und die Antwort ist 0.

+17 versteckte Tests beim Einreichen

Weiterführende Frage

Angenommen, jedes Intervall hat außerdem einen Wert, und du möchtest den größtmöglichen Gesamtwert der sich nicht überlappenden Intervalle erzielen. Funktioniert es immer noch, das Intervall zu behalten, das zuerst endet? Was würdest du stattdessen verwenden?

Lösung

Die möglichst wenigen Intervalle zu entfernen ist dasselbe, wie die größtmögliche Menge an Intervallen zu behalten, die sich nicht überschneiden. Die Antwort ist also n minus diese größte Menge. Alle möglichen Mengen auszuprobieren, die man behalten könnte, hat exponentielle Laufzeit. Dynamische Programmierung über Intervallketten senkt sie auf O(n²). Eine Greedy-Regel erledigt die Aufgabe 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

Dreh die Frage um. Die wenigsten Intervalle zu entfernen bedeutet, die meisten nicht überlappenden Intervalle zu behalten, und die Antwort ist n minus dieser Anzahl. Suche also nach der größten Menge, die du behalten kannst.

Sortiere die Intervalle nach ihrem Startpunkt und entscheide für jedes einzelne der Reihe nach, ob du es entfernst oder behältst. Du darfst es nur behalten, wenn es am oder nach dem Ende des letzten Intervalls beginnt, das du behalten hast. Diese eine Prüfung genügt: Die behaltenen Intervalle bilden dann eine Kette, in der jedes am oder nach dem Ende des vorherigen beginnt, sodass sich keine zwei überlappen. Probiere bei jedem Intervall beide Möglichkeiten aus und nimm das bessere Ergebnis.

Im ersten Beispiel sind die sortierten Intervalle [1,4], [2,3], [3,6], [5,7]. Wenn du [1,4] behältst, blockiert es [2,3] und [3,6], die vor 4 beginnen, und lässt Platz für [5,7]: 2 behaltene Intervalle. Wenn du [1,4] entfernst und [2,3] und dann [3,6] behältst, behältst du ebenfalls 2 Intervalle. Kein Zweig erreicht 3, also entfernst du 4-2 = 2.

Jedes Intervall kann die Anzahl der Zweige verdoppeln, sodass n Intervalle zu bis zu 2^n Pfaden führen. Dreißig Intervalle, die sich nicht überlappen, bedeuten bereits mehr als eine Milliarde Aufrufe, und die Tests gehen bis zu 5000 Intervallen. Die Rekursion geht außerdem n Ebenen tief: 5000 Aufrufe bei den größten Tests, mehr als Pythons Standardgrenze von 1.000.

Algorithmus

Sortiere die Intervalle nach ihrem Start und behalte jeden Start zusammen mit seinem eigenen Ende.
Definiere mostKept(i, last): die meisten Intervalle, die du ab Position i behalten kannst, wenn last die Position des zuletzt behaltenen Intervalls ist (-1, wenn keines behalten wurde).
Gib hinter dem Ende der Liste 0 zurück. Beginne andernfalls mit mostKept(i+1, last), dem Ergebnis, wenn Intervall i entfernt wird.
Wenn Intervall i am Ende von Intervall last oder danach beginnt, probiere auch 1 + mostKept(i+1, i) aus und behalte das größere Ergebnis.
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 obige Suche beantwortet immer wieder dieselbe Frage: Was ist die längste Kette, die mit diesem Intervall endet? Speichere diese Antwort einmal pro Intervall. Sortiere nach Start, und sei chain[i] die größte Anzahl an Intervallen, die du behalten kannst, wenn Intervall i das letzte behaltene Intervall ist.

Das Intervall, das direkt vor i behalten wird, muss bei oder vor starts[i] enden. Jedes solche Intervall kommt in der sortierten Reihenfolge früher: Es beginnt vor seinem Ende, also beginnt es vor starts[i]. Daraus ergibt sich chain[i] = 1 + chain[j] für das beste frühere j mit ends[j] ≤ starts[i], oder 1, wenn kein Intervall passt. Der größte Wert in chain ist die größte Anzahl, die du behalten kannst.

Im ersten Beispiel, sortiert als [1,4], [2,3], [3,6], [5,7], lauten die Werte 1, 1, 2 und 2: [3,6] kann auf [2,3] folgen, und [5,7] kann auf [1,4] oder [2,3] folgen. Die längste Kette hat die Länge 2, also entfernst du 4-2 = 2.

Jedes Intervall betrachtet alle Intervalle davor, was n(n-1)/2 Prüfungen ergibt. Bei n = 5000 sind das etwa 12,5 Millionen Prüfungen: in einer kompilierten Sprache in Ordnung, für die größten Tests in den langsameren Sprachen zu langsam und weit hinter dem folgenden Greedy-Ansatz.

Algorithmus

Sortiere die Intervalle nach ihrem Start und behalte dabei jeden Start bei seinem eigenen Ende.
Setze chain[i] = 1 für jedes Intervall.
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

Betrachte das Intervall mit dem kleinsten Ende. Eine optimale Lösung behält es immer. Nimm eine beliebige größtmögliche Menge von Intervallen, die du behalten kannst, und tausche ihr frühestes Intervall gegen dieses aus. Das neue Intervall endet nicht später als das ersetzte, also endet es weiterhin am oder vor dem Start des nächsten behaltenen Intervalls. Die Menge bleibt überschneidungsfrei und behält ihre Größe, daher kostet es dich nichts, das Intervall mit dem frühesten Ende zu behalten.

Sobald du es behältst, überschneidet sich jedes Intervall, das vor seinem Ende beginnt, mit ihm und muss entfernt werden. Übrig bleibt dieselbe Frage für die Intervalle, die an oder nach diesem Ende beginnen, also wende dieselbe Regel erneut an. In der Praxis: Sortiere nach Ende, gehe die Liste durch und merke dir lastEnd, das Ende des letzten behaltenen Intervalls. Behalte ein Intervall, das an oder nach lastEnd beginnt; zähle jedes andere Intervall als entfernt.

Das erste Beispiel, nach Ende sortiert, lautet [2,3], [1,4], [3,6], [5,7]. Behalte [2,3], also lastEnd = 3. [1,4] beginnt bei 1, also vor 3: Entferne es. [3,6] beginnt bei 3, also nicht vor 3: Behalte es, lastEnd = 6. [5,7] beginnt bei 5, also vor 6: Entferne es. Zwei entfernt.

Andere Kriterien scheinen verlockend, funktionieren aber nicht. Beim Sortieren nach Start behältst du [0,100], obwohl es [1,2], [3,4] und [5,6] umfasst, und entfernst drei Intervalle statt eines. Das kürzeste Intervall zu behalten funktioniert bei [1,5], [4,7], [6,10] nicht: Das kurze [4,7] überschneidet sich mit den beiden anderen, sodass es zwei Entfernungen kostet, obwohl eine genügt. Das Ende ist das Kriterium, das für alles Folgende den meisten Spielraum lässt.

Das Sortieren kostet O(n log n) und das Durchgehen O(n). Die sortierte Kopie der Intervalle benötigt O(n) Speicherplatz.

Algorithmus

Sortiere die Intervalle nach ihrem Ende und behalte jedes Ende bei seinem zugehörigen Start.
Behalte das erste Intervall bei: Setze lastEnd auf sein Ende und removed auf 0.
Gehe jedes folgende Intervall durch. Wenn es bei lastEnd oder danach beginnt, behalte es bei und setze lastEnd auf sein Ende.
Andernfalls addiere 1 zu removed.
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

Die meisten falschen Antworten entstehen durch den Sortierschlüssel oder durch den Vergleich an einem Berührungspunkt.

Berührende Intervalle als überlappend behandeln. Mit start > lastEnd statt start ≥ lastEnd geht in der Kette [1,2], [2,4], [4,6] das Intervall [2,4] verloren, das genau dort beginnt, wo [1,2] endet, und das Ergebnis lautet 1 statt 0.
Nach dem Start sortieren und bei einer Überlappung immer das frühere Intervall behalten. Ein breites Intervall [0,100] verdrängt dann [1,2], [3,4] und [5,6]. Wenn du nach dem Start sortierst, behalte von zwei überlappenden Intervallen dasjenige, das früher endet.
Jedes Intervall mit seinem Nachbarn in der sortierten Liste vergleichen, statt mit dem zuletzt behaltenen Intervall. Nachdem du [1,4] entfernst, muss das nächste Intervall mit dem Ende von [2,3] verglichen werden, nicht mit 4.
starts und ends als zwei separate Listen sortieren. Jedes Ende muss bei seinem eigenen Start bleiben, sonst vergleichst du einen Start mit dem Ende eines anderen Intervalls.
Zurückgeben, wie viele Intervalle du behältst. Gefragt ist die Anzahl der entfernten Intervalle, also n abzüglich dieser Zahl.

Häufige Fragen4

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

Die Greedy-Lösung sortiert die Intervalle nach ihrem Ende in O(n log n) und durchläuft sie anschließend einmal in O(n), sodass die Gesamtlaufzeit O(n log n) beträgt. Die sortierte Kopie der Intervalle benötigt O(n) Speicherplatz. Die dynamische Programmierung hat eine Laufzeit von O(n²), und alle möglichen Mengen auszuprobieren, die beibehalten werden sollen, hat eine Laufzeit von O(2^n).

Warum führt das Sortieren nach Endzeit zu den wenigsten Löschungen?

Das Intervall, das zuerst endet, kann das erste Intervall jeder optimalen Lösung ersetzen, ohne eine Überschneidung zu erzeugen, da es nicht später endet. Eine optimale Lösung enthält es also weiterhin, und nachdem alles entfernt wurde, was sich mit ihm überschneidet, bleibt dasselbe Problem für eine kleinere Menge übrig. Durch Wiederholung des Arguments zeigt sich, dass jede gierige Wahl sicher ist.

Kannst du stattdessen nach Startzeit sortieren?

Ja, mit einer anderen Regel für Überschneidungen. Gehe die Intervalle nach Start durch. Wenn sich das nächste Intervall mit dem zuletzt behaltenen überschneidet, zähle eine Entfernung und behalte dasjenige der beiden Intervalle, das früher endet. Dabei werden genauso viele Intervalle entfernt wie beim Sortieren nach Ende, und der Algorithmus läuft 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 geht es darum, möglichst viele Intervalle zu finden, die sich nicht überlappen; bei diesem Problem geht es darum, möglichst wenige zu entfernen, also n minus dieser Anzahl. Dieselbe gierige Regel, die Aktivität beizubehalten, die zuerst endet, löst beide Probleme.

Python

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

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

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

Erwartet

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 Fragen4

Ähnliche Aufgaben