LeetCode-Meditationen: Intervall einfügen

Die Beschreibung für „Intervall einfügen“ ist recht erklärend:

Sie erhalten ein Array nicht überlappender Intervalle, wobei Intervalle[i] = [start_i, end_i] den Anfang und das Ende des i-ten Intervalls darstellen und die Intervalle in aufsteigender Reihenfolge nach start_i sortiert sind. Sie erhalten außerdem ein Intervall newInterval = [start, end], das den Anfang und das Ende eines anderen Intervalls darstellt.

Fügen Sie newInterval so in Intervalle ein, dass die Intervalle immer noch in aufsteigender Reihenfolge nach start_i sortiert sind und die Intervalle immer noch keine überlappenden Intervalle aufweisen (überlappende Intervalle bei Bedarf zusammenführen).

Rückgabeintervalle nach dem Einfügen.

Beachten Sie, dass Sie die Intervalle nicht vor Ort ändern müssen. Sie können ein neues Array erstellen und es zurückgeben.

Zum Beispiel:

Input: intervals = [[1, 3], [6, 9]], newInterval = [2, 5]
Output: [[1, 5], [6, 9]]

Oder:

Input: intervals = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], newInterval = [4, 8]
Output: [[1, 2], [3, 10], [12, 16]]

Explanation: Because the new interval [4, 8] overlaps with [3, 5], [6, 7], [8, 10].

---

Wir können mit der Erstellung eines Ergebnisarrays beginnen, das, nun ja, das Ergebnis:
enthält

let result = [];

Dann müssen wir beim Durchgehen aller Intervalle prüfen, ob wir unser neues Intervall vor oder nach dem aktuellen Intervall einfügen sollen, oder, ob sie sich überschneiden und daher zusammengeführt werden müssen.

Wie wir in der Kapiteleinleitung gesehen haben, zwei Intervalle nichtüberlappen, wenn der Anfang des einen unbedingt größer als das Ende des anderen ist oder wenn das Ende des einen unbedingt kleiner ist als der Start des anderen.

Wenn diese beiden Fälle falsch sind, überschneiden sie sich.

Zuerst können wir prüfen, ob newInterval vor Intervall kommt. Tatsächlich können wir, wenn wir zuerst dies überprüfen (die „früheste“ Position, die wir finden können, um newInterval zu platzieren), sofort mit unserem neu konstruierten Ergebnis zurückkehren.
Dies ist auch der gierige Ansatz.

for (let i = 0; i < intervals.length; i++) {
  const interval = intervals[i];

  // newInterval is before interval
  if (newInterval[1] < interval[0]) {
    result.push(newInterval);
    return [...result, ...intervals.slice(i)];
  }
  /* ... */  
}

Wenn newInterval jedoch nach dem aktuellen Intervall kommt, das wir betrachten, können wir das aktuelle Intervall einfach auf unser Ergebnis verschieben:

for (let i = 0; i < intervals.length; i++) {
  /* ... */
  // newInterval is after interval
  else if (newInterval[0] > interval[1]) {
    result.push(interval);
  }
}

Die letzte Option besteht darin, dass sie sich überschneiden. In diesem Fall müssen wir die beiden Intervalle zusammenführen. Wir können newInterval erneut mit dem Minimalwert der Intervalle als Anfang und dem Maximalwert als Ende des neuen Intervalls erstellen:

for (let i = 0; i < intervals.length; i++) {
  /* ... */
  // overlapping, create newInterval
  else {
    newInterval = [
      Math.min(newInterval[0], interval[0]),
      Math.max(newInterval[1], interval[1])
    ];
  }
}

Unsere Schleife sieht derzeit so aus:

for (let i = 0; i < intervals.length; i++) {
  const interval = intervals[i];

  // newInterval is before interval
  if (newInterval[1] < interval[0]) {
    result.push(newInterval);
    return [...result, ...intervals.slice(i)] 

  // newInterval is after interval
  } else if (newInterval[0] > interval[1]) {
    result.push(interval);

  // overlapping, create newInterval
  } else {
    newInterval = [Math.min(newInterval[0], interval[0]), Math.max(newInterval[1], interval[1])];
  }
}

Wir müssen auch das neueste newInterval pushen, das wir erstellt haben. Und am Ende können wir einfach das Ergebnis zurückgeben:

function insert(intervals: number[][], newInterval: number[]): number[][] {
  /* ... */
  result.push(newInterval);
  return result;
}

Die Lösung sieht schließlich so aus:

Input: intervals = [[1, 3], [6, 9]], newInterval = [2, 5]
Output: [[1, 5], [6, 9]]

Zeit- und Raumkomplexität

Die zeitliche Komplexität beträgt $O(n)$O(n) da wir für jedes Element im Intervallarray konstante Operationen durchführen. Die räumliche Komplexität wird sein $O(n)$O(n) Außerdem behalten wir ein Ergebnisarray bei, dessen Größe mit zunehmender Länge der Intervalle zunimmt.

---

Als nächstes werfen wir einen Blick auf die Zusammenführungsintervalle. Bis dahin viel Spaß beim Codieren.

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