LeetCode-Meditationen: Intervalle zusammenführen

Beginnen wir mit der Beschreibung für Zusammenführungsintervalle:

Gegeben sei ein Array von Intervallen, wobei Intervalle[i] = [start_i, end_i], alle überlappenden Intervalle zusammenführen und ein Array der nicht überlappenden Intervalle zurückgeben, die alle Intervalle in der Eingabe abdecken.

Zum Beispiel:

Input: intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
Output: [[1, 6], [8, 10], [15, 18]]

Explanation: Since intervals [1, 3] and [2, 6] overlap, merge them into [1, 6].

Oder:

Input: intervals = [[1, 4], [4, 5]]
Output: [[1, 5]]

Explanation: Intervals [1, 4] and [4, 5] are considered overlapping. 

---

Wir können zunächst damit beginnen, die Intervalle zu sortieren, damit wir sie später einfacher vergleichen können:

intervals.sort((a, b) => a[0] - b[0]);

Außerdem können wir ein Ergebnisarray initialisieren, das zunächst das erste Element der neu sortierten Intervalle enthält:

let result = [intervals[0]];

Wir müssen das Ende des letzten zusammengeführten Intervalls verfolgen, um es mit dem Anfang des aktuellen Intervalls zu vergleichen, das wir betrachten, um zu überprüfen, ob sie sich überschneiden.

Hinweis Damit sich zwei Intervalle nicht überschneiden, sollte der

Note

For two intervals not to overlap, the start of one should be strictly larger than the end of the other or the end of the one should be strictly smaller than the start of the other, as mentioned in our chapter introduction.

Anfang eines Intervalls strikt größer sein als das Ende von das andere oder das Ende des einen sollte streng kleiner sein als das Anfangdes anderen, wie in unserer Kapiteleinleitung erwähnt.

Wenn sie sich nicht überschneiden, können wir einfach dieses Intervall zum Ergebnis hinzufügen. Andernfalls müssen wir das „letzte Ende“ aktualisieren und die Intervalle effektiv zusammenführen:

Input: intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
Output: [[1, 6], [8, 10], [15, 18]]

Explanation: Since intervals [1, 3] and [2, 6] overlap, merge them into [1, 6].

Und das Einzige, was noch zu tun bleibt, ist, das Ergebnis zurückzugeben:

Input: intervals = [[1, 4], [4, 5]]
Output: [[1, 5]]

Explanation: Intervals [1, 4] and [4, 5] are considered overlapping. 

Und so sieht unsere endgültige Lösung in TypeScript aus:

intervals.sort((a, b) => a[0] - b[0]);

Zeit- und Raumkomplexität

Wir sortieren Intervalle und die integrierte Sortierfunktion hat $O(nlogn)$O(n log n) Zeitkomplexität. (Die Schleife ist $O(n)$O(n) , aber die Gesamtzeitkomplexität ist $O(nlogn)$O(n log n) ).

Das Ergebnis-Array kann mit zunehmender Größe der Eingabe-Array-Intervalle größer werden, daher haben wir $O(n)$O(n) Raumkomplexität.

---

Als nächstes werfen wir einen Blick auf das letzte Problem im Kapitel „Nicht überlappende Intervalle“. Bis dahin viel Spaß beim Codieren.

Das obige ist der detaillierte Inhalt vonLeetCode-Meditationen: Intervalle zusammenführen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!