Méditations LeetCode : fusionner les intervalles

Commençons par la description des intervalles de fusion :

Étant donné un tableau d'intervalles où intervalles[i] = [start_i, end_i], fusionne tous les intervalles qui se chevauchent et renvoie un tableau d'intervalles qui ne se chevauchent pas qui couvrent tous les intervalles de l'entrée.

Par exemple :

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

Ou :

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

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

---

Nous pouvons commencer par trier les intervalles d'abord, afin de pouvoir les comparer facilement plus tard :

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

De plus, nous pouvons initialiser un tableau de résultats qui contient initialement le premier élément des intervalles nouvellement triés :

let result = [intervals[0]];

Nous devons suivre la fin du dernier intervalle fusionné pour le comparer avec le début de l'intervalle actuel que nous examinons pour vérifier s'ils se chevauchent.

Remarque ête> Pour que deux intervalles ne doivent pas se chevaucher, le

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.

début de l'un doit être strictement plus grand que la fin de l'autre ou l'extrémité de l'un doit être strictement plus petite que la début de l'autre, comme mentionné dans l'introduction de notre chapitre.

S'ils ne se chevauchent pas, nous pouvons simplement ajouter cet intervalle au résultat. Sinon, nous devons mettre à jour la « dernière fin », en fusionnant efficacement les intervalles :

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

Et, il ne reste plus qu'à retourner le résultat :

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

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

Et voici à quoi ressemble notre solution finale dans TypeScript :

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

Complexité temporelle et spatiale

Nous trions les intervalles et la fonction de tri intégrée a $O(nlogn)$O(n log n) complexité temporelle. (La boucle est $O(n)$O(n) , mais la complexité temporelle globale est $O(nlogn)$O(n log n) ).

La taille du tableau de résultats peut augmenter à mesure que la taille des intervalles du tableau d'entrée augmente, nous avons donc $O(n)$O(n) complexité spatiale.

---

Ensuite, nous examinerons le dernier problème du chapitre, Intervalles sans chevauchement. 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!