Méditations LeetCode : Insérer un intervalle

La description d'Insérer un intervalle est assez explicative :

Vous recevez un tableau d'intervalles qui ne se chevauchent pas où intervals[i] = [start_i, end_i] représentent le début et la fin du ième intervalle et les intervalles sont triés par ordre croissant par start_i. Vous recevez également un intervalle newInterval = [start, end] qui représente le début et la fin d'un autre intervalle.

Insérez newInterval dans les intervalles de telle sorte que les intervalles soient toujours triés par ordre croissant par start_i et que les intervalles n'aient toujours pas d'intervalles qui se chevauchent (fusionnez les intervalles qui se chevauchent si nécessaire).

Intervalles de retour après l'insertion.

Notez que vous n'avez pas besoin de modifier les intervalles sur place. Vous pouvez créer un nouveau tableau et le renvoyer.

Par exemple :

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

Ou :

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].

---

Nous pouvons commencer par créer un tableau de résultats pour contenir, eh bien, le résultat :

let result = [];

Ensuite, en parcourant tous les intervalles, nous devons vérifier si nous devons placer notre nouvel intervalle avant ou après l'intervalle actuel, ou, s'ils se chevauchent et doivent donc être fusionnés.

Comme nous l'avons vu dans l'introduction du chapitre, deux intervalles ne se chevauchent si le début de l'un est strictement plus grand que la fin de l'autre, ou, si la fin de l'un est strictement inférieure que le début de l'autre.

Lorsque ces deux cas sont faux, ils se chevauchent.

Tout d'abord, nous pouvons vérifier si newInterval arrive avant l'intervalle. En fait, si nous vérifions d'abord cela (la position "la plus précoce" que nous puissions trouver pour placer newInterval), nous pouvons revenir immédiatement avec notre résultat nouvellement construit.
C'est aussi ça l'approche gourmande.

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)];
  }
  /* ... */  
}

Cependant, si newInterval vient après l'intervalle actuel que nous examinons, nous pouvons simplement pousser l'intervalle actuel vers notre résultat :

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

La dernière option est lorsqu'ils se chevauchent, dans ce cas, nous devons fusionner les deux intervalles. Nous pouvons créer à nouveau newInterval avec la valeur minimale des intervalles comme début, et leur valeur maximale comme fin du nouvel intervalle :

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])
    ];
  }
}

Notre boucle ressemble actuellement à ceci :

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])];
  }
}

Nous devons également pousser le dernier newInterval que nous avons créé. Et, à la fin, on peut simplement renvoyer le résultat :

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

Finalement, la solution ressemble à ceci :

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

Complexité temporelle et spatiale

La complexité temporelle sera $O(n)$O(n) comme nous effectuons des opérations constantes pour chaque élément du tableau d'intervalles. La complexité spatiale sera $O(n)$O(n) De plus, nous conservons un tableau de résultats et sa taille augmentera à mesure que la longueur des intervalles augmente.

---

Ensuite, nous examinerons les intervalles de fusion. En attendant, bon codage.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!