Merge Intervals

Q: Wie hoch ist die Zeitkomplexität von Merge Intervals?

Die Sortier-und-Sweep-Lösung benötigt für n Intervalle O(n log n) Zeit: Das Sortieren kostet O(n log n) und der Sweep O(n). Sie benötigt O(n) zusätzlichen Speicherplatz für die sortierten Paare und das Ergebnis.

Q: Warum sortiert man die Intervalle nach dem Start und nicht nach dem Ende?

Nach Start sortiert kann sich ein Intervall nur mit der Gruppe überschneiden, die du gerade bildest. Daher entscheidet ein Vergleich mit dem Ende dieser Gruppe über alles. Nach Ende sortiert kann ein späteres Intervall vor Gruppen beginnen, die du bereits abgeschlossen hast: [5, 6] kommt vor [1, 10] , und bei einem Vorwärtsdurchlauf würde 5 fälschlicherweise als Start beibehalten.

Q: Kannst du Intervalle ohne zusätzlichen Speicherplatz zusammenführen?

Ja, wenn du die Eingabe ändern darfst. Sortiere die Intervalle direkt im Array, schreibe dann jedes zusammengeführte Intervall über den vorderen Bereich desselben Arrays und behalte den Index des zuletzt geschriebenen Intervalls bei. Die Laufzeit bleibt O(n log n), und der einzige zusätzliche Speicherplatz ist der, den die Sortierfunktion deiner Sprache verwendet.

MittelIntervalle Sortieren

+10

Du erhältst eine Menge von Intervallen, wobei jedes ein Bereich ganzer Zahlen von einem Anfang bis zu einem Ende ist. Fasse jede Gruppe überlappender Intervalle zu einem Intervall zusammen, das die gesamte Gruppe abdeckt, und gib die zusammengefassten Intervalle nach Anfang sortiert zurück. Intervalle, die sich nur berühren, wie [1, 4] und [4, 5], gelten als überlappend.

Die Intervalle werden als zwei Arrays gleicher Länge übergeben: Intervall i ist [starts[i], ends[i]]. Du gibst ein 2D-Array zurück, eine Liste von [start, end]-Paaren.

Funktion

mergeIntervals(starts: integer-array, ends: integer-array) → integer-2d-array

startsinteger-array: der Anfang jedes Intervalls
endsinteger-array: das Ende jedes Intervalls, am selben Index wie sein Anfang
Gibt zurückinteger-2d-array: die zusammengeführten Intervalle als [start, end]-Paare, nach start sortiert

Einschränkungen

1 ≤ starts.length == ends.length ≤ 10⁴
0 ≤ starts[i] ≤ ends[i] ≤ 10⁴
Die Intervalle treffen in beliebiger Reihenfolge ein.
Intervalle, die sich nur an einem Ende berühren, gelten als überlappend.

Beispiele

Eingabe: starts = [5, 1, 12, 3]ends = [7, 4, 14, 6]
Ausgabe: [[1, 7], [12, 14]]
Erklärung: Nach Start sortiert überschneidet sich [1, 4] mit [3, 6], das sich wiederum mit [5, 7] überschneidet, sodass die drei zu [1, 7] zusammengefasst werden. [12, 14] beginnt nach 7 und bleibt für sich.

Weiterführende Frage

Die Intervalle liegen bereits zusammengeführt und nach Start sortiert vor, und du musst ein neues Intervall hinzufügen. Kannst du die zusammengeführte Liste in O(n)-Zeit zurückgeben, ohne erneut zu sortieren?

Lösung

Das Zusammenführen von Paaren in beliebiger Reihenfolge erfordert wiederholte Durchläufe, weil jede Zusammenführung ein Intervall erweitert und es Intervalle erreichen lässt, die du bereits geprüft hast. Sortiere stattdessen nach dem Start. Dann kann ein Intervall nur die Gruppe überlappen, die du gerade erstellst, und ein Durchlauf reicht aus.

Führe überlappende Paare zusammen, bis sich nichts mehr ändert

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

Idee

Die Intervalle [a, b] und [c, d] überlappen sich, wenn c ≤ b und a ≤ d gilt, und [min(a, c), max(b, d)] umfasst beide. Bei jeder Zusammenführung wird ein Intervall entfernt, daher endet der Prozess, und sobald ein vollständiger Durchlauf keine Überlappung findet, haben keine zwei verbleibenden Intervalle einen gemeinsamen Punkt. Ein Durchlauf reicht nicht aus: Ein zusammengeführtes Intervall ist breiter und kann nun ein Intervall erreichen, mit dem sein kleinerer Teil früher im Durchlauf verglichen wurde.

Ein Durchlauf vergleicht etwa n²/2 Paare, und es können bis zu n Durchläufe erforderlich sein: O(n³). Ein Durchlauf über 10^4 Intervalle umfasst bereits 5 × 10^7 Vergleiche.

Algorithmus

Kopiere starts und ends und führe eine Anzahl n aktiver Intervalle.
Vergleiche jedes Intervall i mit jedem späteren Intervall j. Wenn sie sich überschneiden, erweitere i, sodass es j abdeckt, verschiebe das letzte aktive Intervall in Slot j und verringere n um eins.
Prüfe nach einer Zusammenführung Slot j erneut, da sich dort jetzt ein anderes Intervall befindet.
Wiederhole die Durchläufe, bis bei einem Durchlauf keine Zusammenführung stattfindet.
Ordne jeden aktiven Start seinem Ende zu, sortiere die Paare nach dem Start und gib sie zurück.

def mergeIntervals(starts, ends):
    s = list(starts)
    e = list(ends)
    n = len(s)
    changed = True
    while changed:
        changed = False
        i = 0
        while i < n:
            j = i + 1
            while j < n:
                if s[j] <= e[i] and s[i] <= e[j]:
                    # Intervals i and j overlap: interval i absorbs interval j.
                    s[i] = min(s[i], s[j])
                    e[i] = max(e[i], e[j])
                    # Move the last interval into slot j and drop the last slot.
                    n -= 1
                    s[j] = s[n]
                    e[j] = e[n]
                    changed = True
                else:
                    j += 1
            i += 1
    return sorted([s[k], e[k]] for k in range(n))

Nach Start sortieren und einmal durchlaufen

Idee

Nach dem Sortieren nach dem Start beginnt das nächste Intervall nicht früher als alle Intervalle in der letzten Gruppe, die bei e endet. Wenn sein Start höchstens e beträgt, überschneidet es sich mit der Gruppe oder berührt sie und wird ihr hinzugefügt; e wird zum größeren der beiden Endpunkte. Liegt sein Start hinter e, kann auch kein späteres Intervall die Gruppe mehr erreichen, da spätere Intervalle weiter rechts beginnen. Die Gruppe ist abgeschlossen, und das Intervall eröffnet eine neue.

Das Sortieren kostet O(n log n), und beim Durchlauf wird jedes Intervall genau einmal besucht. Die Gruppen werden von links nach rechts abgeschlossen, sodass das Ergebnis nach Start sortiert ist.

Algorithmus

Ordne jeden Start seinem Ende zu: Das Intervall i ist [starts[i], ends[i]].
Sortiere die Paare nach dem Start.
Gehe die sortierten Paare durch. Wenn das Ergebnis leer ist oder das Paar nach dem Ende des letzten zusammengeführten Intervalls beginnt, füge das Paar als neues Intervall hinzu.
Andernfalls setze das Ende des letzten zusammengeführten Intervalls auf den größeren Wert aus seinem Ende und dem Ende des Paars.
Gib die zusammengeführte Liste zurück.

def mergeIntervals(starts, ends):
    intervals = sorted(zip(starts, ends))
    merged = []
    for start, end in intervals:
        if merged and start <= merged[-1][1]:
            if end > merged[-1][1]:
                merged[-1][1] = end
        else:
            merged.append([start, end])
    return merged

Stolperfallen und Grenzfälle

Vergleich mit < statt mit ≤. Sich berührende Intervalle wie [1, 4] und [4, 5] müssen zusammengeführt werden.
Das Ende auf das Ende des neuen Intervalls setzen, anstatt auf den größeren der beiden Werte. Auf [1, 10] gefolgt von [2, 3] muss [1, 10] erhalten bleiben.
starts separat sortieren und dann ends an den neuen Positionen auslesen, sodass ein Startwert das Ende eines anderen Intervalls erhält. Füge die Werte zuerst zu Paaren zusammen oder sortiere Indizes.
Vergleich mit dem vorherigen Eingabeintervall statt mit dem zuletzt zusammengeführten Intervall. Bei [1, 10], [2, 3], [4, 5] liegt das dritte Intervall innerhalb von [1, 10], obwohl es [2, 3] nicht berührt.
In C *returnSize nicht auf die Anzahl der zusammengeführten Intervalle und die Größe jeder Spalte auf 2 setzen.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität von Merge Intervals?

Die Sortier-und-Sweep-Lösung benötigt für n Intervalle O(n log n) Zeit: Das Sortieren kostet O(n log n) und der Sweep O(n). Sie benötigt O(n) zusätzlichen Speicherplatz für die sortierten Paare und das Ergebnis.

Warum sortiert man die Intervalle nach dem Start und nicht nach dem Ende?

Nach Start sortiert kann sich ein Intervall nur mit der Gruppe überschneiden, die du gerade bildest. Daher entscheidet ein Vergleich mit dem Ende dieser Gruppe über alles. Nach Ende sortiert kann ein späteres Intervall vor Gruppen beginnen, die du bereits abgeschlossen hast: [5, 6] kommt vor [1, 10], und bei einem Vorwärtsdurchlauf würde 5 fälschlicherweise als Start beibehalten.

Kannst du Intervalle ohne zusätzlichen Speicherplatz zusammenführen?

Ja, wenn du die Eingabe ändern darfst. Sortiere die Intervalle direkt im Array, schreibe dann jedes zusammengeführte Intervall über den vorderen Bereich desselben Arrays und behalte den Index des zuletzt geschriebenen Intervalls bei. Die Laufzeit bleibt O(n log n), und der einzige zusätzliche Speicherplatz ist der, den die Sortierfunktion deiner Sprache verwendet.

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

Test #1

Test #2

Argumente

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

Erwartete Ausgabe

[[1, 7], [12, 14]]