LeetCode-Meditationen: Nicht überlappende Intervalle

Die Beschreibung für nicht überlappende Intervalle lautet:

Gegeben ist ein Array von Intervallen, wobei Intervalle[i] = [start_i, end_i] ist. Geben Sie die Mindestanzahl an Intervallen zurück, die Sie entfernen müssen, damit sich die restlichen Intervalle nicht überlappen.

Beachten Sie, dass Intervalle, die sich nur an einem Punkt berühren, nicht überlappend sind. Beispielsweise überlappen sich [1, 2] und [2, 3] nicht.

Zum Beispiel:

Input: intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
Output: 1

Explanation: [1, 3] can be removed and the rest of the intervals are non-overlapping.

Oder:

Input: intervals = [[1, 2], [1, 2], [1, 2]]
Output: 2

Explanation: You need to remove two [1, 2] to make the rest of the intervals non-overlapping.

Oder:

Input: intervals = [[1, 2], [2, 3]]
Output: 0

Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

---

Für dieses Problem hat NeetCode eine großartige Lösung, die mit dem Sortieren der Intervalle beginnt, wie wir es im vorherigen Problem getan haben.
Wir können auch eine Variable initialisieren, um die Anzahl der Entfernungen zu verfolgen.

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

let numRemovals = 0;

Da unsere Intervalle nun sortiert sind, gehen wir jedes einzelne durch und prüfen, ob sie sich überschneiden oder nicht. Dazu behalten wir das Ende des vorherigen Intervalls im Auge, also initialisieren wir eine prevEnd-Variable, die zunächst das Ende des ersten Intervalls enthält:

let prevEnd = intervals[0][1];

Hinweis Damit sich zwei Intervalle

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.

nicht überschneiden, sollte der Anfang des einen strikt größer sein als das Ende des Intervalls other oder das Ende des einen sollte strikt sein kleiner als der Anfang des anderen, wie in unserer Kapiteleinleitung erwähnt.

Wenn bei diesem Problem das Ende eines Intervalls mit dem Anfang des anderen Intervalls übereinstimmt, gelten sie als nicht überlappend.

Hier können wir also sagen, dass sich zwei Intervalle überlappen, wenn der Anfang des einen unbedingt kürzer ist als das Ende des anderen. In diesem Fall aktualisieren wir prevEnd auf den kleineren Wert der beiden Enden, sodass die Wahrscheinlichkeit einer Überlappung mit dem nächsten Intervall geringer ist. Ansonsten machen wir weiter wie bisher:

Input: intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
Output: 1

Explanation: [1, 3] can be removed and the rest of the intervals are non-overlapping.

Endlich können wir numRemovals zurückgeben:

Input: intervals = [[1, 2], [1, 2], [1, 2]]
Output: 2

Explanation: You need to remove two [1, 2] to make the rest of the intervals non-overlapping.

Und die endgültige Lösung, die wir haben, sieht so aus:

Input: intervals = [[1, 2], [2, 3]]
Output: 0

Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

Zeit- und Raumkomplexität

Da wir die Intervalle zu Beginn sortieren, beträgt die zeitliche Komplexität $O(nlogn)$O(n log n) . Wir haben keine zusätzliche Datenstruktur, deren Größe mit zunehmender Eingabegröße zunimmt, daher ist die Platzkomplexität größer $O(1)$O(1) .

---

Als nächstes beginnen wir mit dem letzten Kapitel der Serie, Bit-Manipulation. Bis dahin viel Spaß beim Codieren.

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