Insert Interval

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

Die Lösung mit einem Durchlauf läuft in O(n) Zeit: Jedes Intervall wird genau einmal kopiert oder zusammengeführt. Das Ergebnis enthält bis zu n+1 Intervalle und benötigt daher O(n) Speicherplatz; nichts anderes wächst mit der Eingabe. Das Intervall hinzuzufügen und die Intervalle erneut zu sortieren, dauert stattdessen 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 muss zuerst sortiert werden. Bei Insert Interval ist die Liste bereits sortiert und die alten Intervalle berühren sich nie, daher kann nur das neue Intervall eine Zusammenführung auslösen. Die Intervalle, mit denen es zusammengeführt wird, bilden einen ununterbrochenen Abschnitt. Deshalb reicht ein einziger Durchlauf ohne Sortieren aus.

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

Intervalle [a, b] und [c, d] haben genau dann mindestens einen gemeinsamen Punkt, wenn a ≤ d und c ≤ b gilt. Dadurch zählen auch sich berührende Intervalle wie [2, 4] und [4, 8] als überlappend, was in dieser Aufgabe gewünscht ist. Wenn sich berührende Intervalle getrennt bleiben müssten, würde man stattdessen a < d und c < b verwenden.

Q: Kann die binäre Suche Insert Interval schneller machen?

Die binäre Suche findet in O(log n) , wo der zusammengeführte Bereich beginnt und endet, da sowohl die Start- als auch die Endpunkte sortiert sind. Die Funktion gibt jedoch weiterhin eine neue Liste zurück, und das Kopieren der unveränderten Intervalle kostet O(n) . Die Gesamtlaufzeit bleibt also O(n) . Die binäre Suche lohnt sich, wenn die Intervalle in einer Datenstruktur gespeichert sind, die einen Bereich ohne Kopieren entfernen und einfügen kann, etwa in einem balancierten Baum.

MittelIntervalle

+10

Du erhältst eine nach Start sortierte Liste von Intervallen, dargestellt durch zwei Arrays gleicher Länge: Intervall i ist [starts[i], ends[i]]. Keine zwei davon überlappen sich oder berühren sich. Außerdem erhältst du ein neues Intervall, [newStart, newEnd]. Füge es ein, führe es mit jedem Intervall zusammen, das es überlappt oder berührt, und gib alle Intervalle als 2D-Array von [start, end]-Paaren zurück, sortiert nach Start.

Zwei Intervalle berühren sich, wenn eines dort endet, wo das andere beginnt, wie bei [2, 4] und [4, 8]; sich berührende Intervalle werden zu einem 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 Startpunkte
newStartinteger: der Beginn 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, sortiert nach start

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 überschneiden 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, daher 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. Berührungen zählen als Überschneidungen, also werden alle drei zu [2, 9] zusammengeführt.

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.

+20 versteckte Tests beim Einreichen

Weiterführende Frage

Angenommen, du fügst nacheinander viele neue Intervalle in dieselbe Liste ein. Wie würdest du die Intervalle speichern, sodass jeder Einfügevorgang O(log n) plus einen Schritt für jedes alte Intervall kostet, das er verschlingt?

Tipps

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

0 von 3 geöffnet

Lösung

Die alten Intervalle liegen bereits getrennt und geordnet vor, daher kann nur das neue Intervall eine Zusammenführung verursachen. Dadurch wird die Liste in drei Abschnitte unterteilt: Intervalle, die enden, bevor das neue beginnt, Intervalle, die es überlappen oder berühren, und Intervalle, die beginnen, nachdem es endet. Kopiere den ersten Abschnitt, fasse den mittleren Abschnitt zu einem einzigen Intervall zusammen und kopiere den letzten Abschnitt. Ein Durchlauf, kein Sortieren.

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

Idee

Wenn du Merge Intervals gelöst hast, kannst du die Lösung hier wiederverwenden. Füge das neue Intervall in die Liste ein, sortiere alle n+1 Intervalle nach dem Start und führe sie zusammen. Nach dem Sortieren kann ein Intervall nur die Gruppe direkt davor überlappen, also gehst du die Liste durch und behältst dabei das zuletzt zusammengeführte Intervall im Blick. Wenn der nächste Startpunkt kleiner oder gleich seinem Ende ist, verlängerst du das Ende. Andernfalls gibt es eine echte Lücke und ein neues Intervall beginnt.

Führe das am ersten Beispiel aus. Die Liste wird zu [1, 3], [5, 7], [6, 11], [10, 12], [15, 18]. [1, 3] bleibt für sich, da 5 größer als 3 ist. 6 ist kleiner oder gleich 7, also wird [5, 7] zu [5, 11] verlängert. 10 ist kleiner oder gleich 11, also wird es zu [5, 12] verlängert. 15 ist größer als 12, also beginnt [15, 18] ein neues Intervall.

Das ist korrekt, und bei 2000 Intervallen läuft es schnell. Dabei lässt du allerdings zwei Fakten außer Acht, die dir gegeben wurden: Die Liste ist bereits sortiert und die alten Intervalle werden nie miteinander zusammengeführt. O(n log n) dafür aufzuwenden, eine Liste neu zu sortieren, die nur an einer Stelle ungeordnet ist, ist der Schritt, den ein Interviewer dich auffordern wird zu entfernen.

Algorithmus

Ordne jedem Start sein Ende zu und füge [newStart, newEnd] zur Liste hinzu.
Sortiere die Intervalle nach ihrem Start.
Gehe sie der Reihe nach durch und behalte das zuletzt zusammengeführte Intervall im Blick.
Wenn der nächste Start höchstens dem gehaltenen Ende entspricht, setze das gehaltene Ende auf das größere der beiden Enden.
Andernfalls füge 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

Gehe die Liste mit einem Index i einmal durch und teile sie in drei Abschnitte auf. Zuerst endet jedes Intervall mit ends[i] < newStart vor dem Beginn des neuen Intervalls und hat daher keinen gemeinsamen Punkt mit ihm: Kopiere es in das Ergebnis. Der Test verwendet ein striktes <, weil ein Intervall, das genau bei newStart endet, das neue Intervall berührt und zusammengeführt werden muss.

Zweitens überschneidet sich jedes Intervall mit starts[i] ≤ mergedEnd mit dem Intervall, das du gerade bildest, oder berührt es. Füge es zusammen: mergedStart wird zum kleineren Anfang und mergedEnd zum größeren Ende. Die Intervalle in diesem Abschnitt liegen nebeneinander, weil die Liste sortiert ist. Sobald ein Intervall nach mergedEnd beginnt, beginnt jedes spätere noch weiter rechts, sodass nichts danach zusammengeführt werden kann. Füge das zusammengeführte Intervall hinzu; dieser Schritt deckt auch den Fall ab, dass der Abschnitt leer ist und das neue Intervall allein eingefügt wird.

Drittens kopierst du alles, was übrig ist. Diese Intervalle beginnen nach dem Ende des zusammengeführten Intervalls und lagen bereits getrennt voneinander.

Gehe das erste Beispiel durch. [1, 3] endet vor 6: Kopiere es. [5, 7] beginnt bei 5, also höchstens bei 11: Das zusammengeführte Intervall wird zu [5, 11]. [10, 12] beginnt bei 10, also höchstens bei 11: Es wird zu [5, 12]. [15, 18] beginnt nach 12, also füge [5, 12] hinzu und kopiere [15, 18]. Jedes Intervall wird einmal betrachtet, daher beträgt die Laufzeit O(n), und der einzige zusätzliche Speicher ist das Ergebnis selbst.

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 Start und mergedEnd auf das größere Ende 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

Die Schleife ist kurz, daher entstehen die meisten Fehler durch einen falschen Vergleich oder einen vergessenen Fall an den Enden der Liste.

Die falsche Ungleichung für sich berührende Intervalle verwenden. Mit ends[i] ≤ newStart in der ersten Schleife oder starts[i] < mergedEnd in der zweiten bleiben [2, 4] und [4, 8] getrennt. Sich berührende Intervalle werden zusammengeführt, daher ist der erste Test strikt und der zweite nicht.
Intervalle zusammenführen, die nur benachbart aussehen. [1, 2] und [3, 4] haben keinen gemeinsamen Punkt, daher führt ein Vergleich mit mergedEnd + 1 Intervalle zusammen, die getrennt bleiben sollten.
newStart als Anfang des zusammengeführten Intervalls beibehalten. Wenn das neue Intervall innerhalb eines alten beginnt, wie [6, 11] innerhalb von [5, 7], beginnt das Ergebnis bei 5. Nimm den kleineren der beiden Startwerte.
Das neue Intervall nur hinzufügen, wenn es sich mit einem anderen überschneidet. Liegt es vor allen Intervallen, nach allen Intervallen oder in einer Lücke, wird die mittlere Schleife nie ausgeführt, und das neue Intervall muss trotzdem hinzugefügt werden.
starts[i] oder ends[i] lesen, bevor i < n geprüft wird. Wenn das neue Intervall über das letzte Intervall hinausreicht, läuft der Index über das Ende der Arrays hinaus.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität von Insert Interval?

Die Lösung mit einem Durchlauf läuft in O(n) Zeit: Jedes Intervall wird genau einmal kopiert oder zusammengeführt. Das Ergebnis enthält bis zu n+1 Intervalle und benötigt daher O(n) Speicherplatz; nichts anderes wächst mit der Eingabe. Das Intervall hinzuzufügen und die Intervalle erneut zu sortieren, dauert stattdessen 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 muss zuerst sortiert werden. Bei Insert Interval ist die Liste bereits sortiert und die alten Intervalle berühren sich nie, daher kann nur das neue Intervall eine Zusammenführung auslösen. Die Intervalle, mit denen es zusammengeführt wird, bilden einen ununterbrochenen Abschnitt. Deshalb reicht ein einziger Durchlauf ohne Sortieren aus.

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

Intervalle [a, b] und [c, d] haben genau dann mindestens einen gemeinsamen Punkt, wenn a ≤ d und c ≤ b gilt. Dadurch zählen auch sich berührende Intervalle wie [2, 4] und [4, 8] als überlappend, was in dieser Aufgabe gewünscht ist. Wenn sich berührende Intervalle getrennt bleiben müssten, würde man stattdessen a < d und c < b verwenden.

Kann die binäre Suche Insert Interval schneller machen?

Die binäre Suche findet in O(log n), wo der zusammengeführte Bereich beginnt und endet, da sowohl die Start- als auch die Endpunkte sortiert sind. Die Funktion gibt jedoch weiterhin eine neue Liste zurück, und das Kopieren der unveränderten Intervalle kostet O(n). Die Gesamtlaufzeit bleibt also O(n). Die binäre Suche lohnt sich, wenn die Intervalle in einer Datenstruktur gespeichert sind, die einen Bereich ohne Kopieren entfernen und einfügen kann, etwa in einem balancierten Baum.

Python

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

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

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

Erwartet

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