Insert Interval

Q: Wie hoch ist die zeitliche Komplexität von Insert Interval?

Die Lösung mit einem Durchlauf benötigt O(n) Zeit, da jedes Intervall genau einmal kopiert oder zusammengeführt wird, und O(n) Speicherplatz für ein Ergebnis mit bis zu n+1 Intervallen. Das Hinzufügen des Intervalls und erneute Sortieren benötigt O(n log n) .

Q: Worin unterscheidet sich Insert Interval von Merge Intervals?

Merge Intervals beginnt mit einer unsortierten Liste, in der sich beliebige Intervalle überschneiden können, daher wird sie zunächst sortiert. Hier ist die Liste sortiert und die alten Intervalle berühren sich nie, daher kann nur das neue Intervall eine Zusammenführung auslösen, und die Intervalle, mit denen es zusammengeführt wird, bilden eine zusammenhängende Folge. Ein einziger Durchlauf genügt.

Q: Wie überprüfst du, ob sich zwei Intervalle überschneiden?

[a, b] und [c, d] haben genau dann einen gemeinsamen Punkt, wenn a ≤ d und c ≤ b gilt. Dadurch zählen sich berührende Intervalle wie [2, 4] und [4, 8] als überlappend, wie es in dieser Aufgabe gewünscht ist. Damit sich berührende Intervalle getrennt bleiben, verwende a < d und c < b .

MittelIntervalle

+10

Du erhältst Intervalle, die nach ihrem Start sortiert sind, als zwei Arrays: Intervall i ist [starts[i], ends[i]], und keine zwei Intervalle überschneiden sich oder berühren sich. Füge das neue Intervall [newStart, newEnd] ein, führe es mit jedem Intervall zusammen, das es überschneidet oder berührt, und gib alle Intervalle als [start, end]-Paare zurück, sortiert nach ihrem Start.

Intervalle berühren sich, wenn eines dort endet, wo das andere beginnt, wie bei [2, 4] und [4, 8], und sich berührende Intervalle werden zusammengeführt. [1, 2] und [3, 4] haben keinen gemeinsamen Punkt und bleiben daher getrennt.

Funktion

insertInterval(starts: integer-array, ends: integer-array, newStart: integer, newEnd: integer) → integer-2d-array

startsinteger-array: den Anfang jedes Intervalls, in aufsteigender Reihenfolge
endsinteger-array: das Ende jedes Intervalls, passende Starts
newStartinteger: der Anfang des einzufügenden Intervalls
newEndinteger: das Ende des einzufügenden Intervalls
Gibt zurückinteger-2d-array: die Intervalle nach dem Einfügen als [start, end]-Paare, nach start sortiert

Einschränkungen

1 ≤ starts.length == ends.length ≤ 2000
0 ≤ starts[i] ≤ ends[i] ≤ 10⁵
ends[i] < starts[i+1]: Die Intervalle sind nach ihrem Start sortiert, und keine zwei davon überlappen sich oder berühren sich.
0 ≤ newStart ≤ newEnd ≤ 10⁵

Beispiele

Eingabe: starts = [1, 5, 10, 15]ends = [3, 7, 12, 18]newStart = 6newEnd = 11
Ausgabe: [[1, 3], [5, 12], [15, 18]]
Erklärung: [6, 11] überschneidet sich mit [5, 7] und [10, 12], sodass die drei zu [5, 12] zusammengeführt werden. [1, 3] endet vor 6 und [15, 18] beginnt nach 12, also bleiben beide unverändert.

Eingabe: starts = [2, 8]ends = [4, 9]newStart = 4newEnd = 8
Ausgabe: [[2, 9]]
Erklärung: [4, 8] berührt [2, 4] bei 4 und [8, 9] bei 8, sodass alle drei zu [2, 9] zusammengeführt werden.

Eingabe: starts = [1, 9]ends = [2, 10]newStart = 5newEnd = 6
Ausgabe: [[1, 2], [5, 6], [9, 10]]
Erklärung: [5, 6] liegt in der Lücke zwischen 2 und 9 und berührt keinen der beiden Nachbarn, also wird es dazwischen eingefügt und nichts wird zusammengeführt.

Weiterführende Frage

Wenn du viele Intervalle nacheinander einfügst, wie würdest du sie speichern, sodass jeder Einfügevorgang O(log n) plus einen Schritt pro altem Intervall kostet, das er verschluckt?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Die alten Intervalle sind sortiert und voneinander getrennt, daher kann nur das neue Intervall eine Zusammenführung verursachen. Dadurch wird die Liste in drei Abschnitte aufgeteilt: Intervalle, die enden, bevor es beginnt, Intervalle, die sich mit ihm überschneiden oder es berühren, und Intervalle, die beginnen, nachdem es endet. Kopiere den ersten Abschnitt, fasse den mittleren Abschnitt zu einem Intervall zusammen und kopiere den letzten. Ein Durchlauf, kein Sortieren.

Füge es hinzu und führe alles wieder zusammen

Idee

Wiederverwendung von Merge Intervals: Füge das neue Intervall hinzu, sortiere alle n+1 Intervalle nach dem Start und gehe sie durch, wobei du das letzte zusammengeführte Intervall festhältst. Nach dem Sortieren kann ein Intervall nur die Gruppe direkt davor überlappen. Wenn der nächste Start also am oder vor dem festgehaltenen Ende liegt, erweitere das Ende; andernfalls entsteht eine Lücke und ein neues Intervall beginnt.

Das Sortieren kostet O(n log n), um eine Liste zu ordnen, die an einer Stelle durcheinandergeraten ist, und berücksichtigt nicht, dass die alten Intervalle nie miteinander zusammengeführt werden.

Algorithmus

Ordne jedem Start das passende Ende zu und füge [newStart, newEnd] zur Liste hinzu.
Sortiere die Intervalle nach ihrem Start.
Gehe sie der Reihe nach durch und behalte dabei das zuletzt zusammengeführte Intervall im Blick.
Wenn der nächste Start höchstens dem gespeicherten Ende entspricht, setze das gespeicherte Ende auf den größeren der beiden Endwerte.
Füge andernfalls das nächste Intervall als neues zusammengeführtes Intervall hinzu. Gib die zusammengeführte Liste zurück.

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

Ein Durchlauf in drei Teilen

Idee

Die Liste ist sortiert und ihre Intervalle liegen getrennt voneinander, sodass die Intervalle, die das neue Intervall berühren, eine zusammenhängende Folge bilden. Alles vor dieser Folge erfüllt ends[i] < newStart: Es endet, bevor das neue Intervall beginnt. Die Bedingung ist strikt, weil ein Intervall, das genau bei newStart endet, das neue Intervall berührt und zusammengeführt werden muss.

Innerhalb der Folge überschneidet sich ein Intervall mit starts[i] ≤ mergedEnd mit dem Intervall, das du gerade bildest, oder berührt es. Dadurch wird es auf den kleineren Startwert und den größeren Endwert erweitert. Das erste Intervall, das nach mergedEnd beginnt, beendet die Folge, da jedes spätere weiter rechts beginnt. Ist die Folge leer, wird das neue Intervall allein eingefügt. Im ersten Beispiel wird [1, 3] kopiert, [5, 7] und [10, 12] erweitern [6, 11] zu [5, 12], und [15, 18] wird kopiert. Jedes Intervall wird einmal betrachtet: Zeitaufwand O(n) und kein zusätzlicher Speicher über das Ergebnis hinaus.

Algorithmus

Kopiere Intervalle in das Ergebnis, solange ends[i] < newStart.
Setze mergedStart = newStart und mergedEnd = newEnd.
Solange starts[i] ≤ mergedEnd, setze mergedStart auf den kleineren Startwert und mergedEnd auf den größeren Endwert und fahre fort.
Füge [mergedStart, mergedEnd] hinzu.
Kopiere die verbleibenden Intervalle und gib das Ergebnis zurück.

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

Stolperfallen und Grenzfälle

Falsche Ungleichungen bei sich berührenden Intervallen. Mit ends[i] ≤ newStart in der ersten Schleife oder starts[i] < mergedEnd in der zweiten bleiben [2, 4] und [4, 8] getrennt. Der erste Test ist strikt, der zweite nicht.
Vergleichen mit mergedEnd + 1. Dadurch werden [1, 2] und [3, 4] zusammengeführt, obwohl sie keinen gemeinsamen Punkt haben.
newStart als Anfang des zusammengeführten Intervalls beibehalten. [6, 11] beginnt innerhalb von [5, 7], daher beginnt das Ergebnis bei 5.
Das neue Intervall nur hinzufügen, wenn es etwas überlappt. Wenn es in eine Lücke oder über eines der beiden Enden hinausfällt, wie bei [5, 6], wird die mittlere Schleife nie ausgeführt, und es muss trotzdem hinzugefügt werden.
starts[i] lesen, bevor i < n geprüft wird. Ein neues Intervall, das über das letzte hinausreicht, lässt den Index über das Ende hinauslaufen.

Häufige Fragen3

Wie hoch ist die zeitliche Komplexität von Insert Interval?

Die Lösung mit einem Durchlauf benötigt O(n) Zeit, da jedes Intervall genau einmal kopiert oder zusammengeführt wird, und O(n) Speicherplatz für ein Ergebnis mit bis zu n+1 Intervallen. Das Hinzufügen des Intervalls und erneute Sortieren benötigt O(n log n).

Worin unterscheidet sich Insert Interval von Merge Intervals?

Merge Intervals beginnt mit einer unsortierten Liste, in der sich beliebige Intervalle überschneiden können, daher wird sie zunächst sortiert. Hier ist die Liste sortiert und die alten Intervalle berühren sich nie, daher kann nur das neue Intervall eine Zusammenführung auslösen, und die Intervalle, mit denen es zusammengeführt wird, bilden eine zusammenhängende Folge. Ein einziger Durchlauf genügt.

Wie überprüfst du, ob sich zwei Intervalle überschneiden?

[a, b] und [c, d] haben genau dann einen gemeinsamen Punkt, wenn a ≤ d und c ≤ b gilt. Dadurch zählen sich berührende Intervalle wie [2, 4] und [4, 8] als überlappend, wie es in dieser Aufgabe gewünscht ist. Damit sich berührende Intervalle getrennt bleiben, verwende a < d und c < b.

def insertInterval(starts, ends, newStart, newEnd):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argumente

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

Erwartete Ausgabe

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