- Le rituel TAP. Invariant, variant, conclusion, complexité — c00, pas 1. La boucle est ici un balayage simple : un tour par intervalle, jamais de retour en arrière, et le tri se raconte avant la boucle.
- Invariant = conteneur + tranche + « exactement ». c00, pas 2. Le conteneur est ici la liste de sortie et non une variable scalaire : c'est ce déplacement qui fait toute la difficulté du pas 3.
- Variant = entier ≥ 0 strictement décroissant. c00, pas 3. C'est n − i, le nombre d'intervalles non encore lus. Pas la longueur de
merged, qui croît. - Complexité composée. c00, pas 5. O(n log n) est ici une somme dominée par un terme, pas un produit : tri + balayage, et le balayage disparaît dans le tri.
- Le tri comme achat. c02, pas 3. Là le tri autorisait à éliminer une moitié du plan ; ici il autorise à oublier tout le passé sauf une borne. Même dépense, deux dividendes différents.
<= ou un <, et deux réponses différentes — pas 6.
H3On peut trier : les n intervalles tiennent en mémoire et sont tous connus avant de commencer. Sur un flux, rien de ce qui suit ne tient — le tri est l'hypothèse cachée du pattern.
H4On énonce le squelette et les phrases. Le corps se remplit devant l'interlocuteur : une sheet de coding ne contient jamais la solution complète.
La chaîne
Le signal, et le contre-signal tronc
Des paires qu'on peut lire comme [début, fin] sur un même axe : réunions, réservations, plages, versions valides de… à…. Et une question qui porte sur leur recouvrement : fusionner, insérer, compter les simultanées, en retirer le moins possible, mesurer la couverture.
Le contre-signal est géométrique : dès que les segments ne sont plus sur une droite, l'ordre total disparaît et le pattern avec lui. Sur un cercle (23 h – 2 h) et en 2D (rectangles), « trier par début » ne veut plus rien dire.
« On me donne des segments d'un même axe et une question de recouvrement, donc l'ordre dans lequel ils arrivent ne porte aucune information, donc je commence par les ranger sur l'axe, donc la question devient un balayage de gauche à droite. »
Le fil rouge. intervals = [[1,3],[2,6],[8,10],[9,12],[15,18]], déjà trié par début. La fusion donne [[1, 6], [8, 12], [15, 18]] : cinq intervalles en entrée, trois en sortie, deux fusions. Somme des longueurs brutes 14, couverture réelle 12 — l'écart de 2 est exactement ce que le double comptage aurait ajouté.
Pourquoi cinq et pas quatre. C'est l'exemple de LeetCode 56 avec un intervalle de plus, [9,12], glissé exprès : il force une deuxième fusion, et surtout une fusion dont la fin dépasse celle du dernier fusionné (12 > 10). Sans lui, le max du squelette passerait inaperçu.
Le contre-signal, chiffré. Sur un cercle, une réunion 23 h – 2 h se lit [23, 2] avec fin < début : le tri par début la place après tout le monde et le balayage ne la voit jamais chevaucher le créneau de minuit. Le remède se dit en une phrase — couper en deux, [23, 24] et [0, 2] — et il rend au problème son axe.
Ce que la sheet n'aborde pas. Les arbres d'intervalles, les segment trees, le balayage 2D de rectangles. On les nomme si la question tombe ; ici, une seule liste et un seul passage.
Le pattern : le tri achète « le dernier suffit » tronc
Après le tri par début, le balayage ne regarde qu'un seul intervalle de tout ce qu'il a déjà construit : le dernier de merged. L'énoncé du pattern n'est pas « le dernier suffit » — c'est pourquoi il suffit :
Les fusionnés antérieurs finissent avant le début du dernier — ils sont hors d'atteinte. Le test est alors binaire : prolonger (fin = max) ou ouvrir.
« Les débuts sont croissants, donc tout intervalle à venir commence après le début du dernier fusionné, donc il ne peut atteindre aucun fusionné antérieur, donc comparer au seul dernier suffit : je prolonge sa fin ou j'en ouvre un nouveau. »
Six lignes, et une seule porte l'idée : s <= merged[-1].fin. Toute la mémoire du balayage tient dans ce nombre unique — la fin du dernier fusionné. Les i − 1 intervalles déjà rangés ne sont plus jamais relus.
Le max n'est pas décoratif. Au tour 3 du fil rouge, [9,12] rencontre [8,10] : la fin devient max(10, 12) = 12, elle grandit. Au tour 1, [2,6] rencontre [1,3] : max(3, 6) = 6, elle grandit aussi. Mais un intervalle inclus, comme [2,3] dans [1,10], donne max(10, 3) = 10 : sans le max, la fin reculerait et la sortie perdrait 3 unités de couverture sans lever d'erreur.
Ce que le tri ne garantit pas. Les fins, elles, ne sont pas croissantes : sur le fil rouge trié elles valent 3, 6, 10, 12, 18 — croissantes ici par hasard, et pas en général ([1,10] puis [2,3]). C'est pour cela que la fin du dernier se calcule par un max et ne se lit pas dans l'entrée.
Les cinq intervalles triés, en haut ; la liste merged en construction, en bas et en vert. Fais « pas › ». À chaque image, la barre rouge est l'intervalle du tour et le trait vertical pointillé marque merged[-1].fin — le seul nombre que l'algorithme retient. Regarde uniquement ce trait : si le début rouge tombe à gauche ou dessus, la barre verte s'allonge ; s'il tombe à droite, une barre verte s'ouvre. Arrête-toi à l'image 5, la seule qui prouve quelque chose : [9,12] prolonge [8,10] et la frontière saute de 10 à 12, c'est le max en action. Et note ce qui ne se produit jamais : la barre rouge ne revient jamais chevaucher une barre verte antérieure à la dernière — pas par chance, mais parce que son début est ≥ tous les débuts déjà lus. C'est cette impossibilité que le tri a achetée.
L'invariant, le variant, la conclusion tronc
L'invariant porte sur la liste de sortie, pas sur une variable, et le mot qui porte tout est exactement :
Trois clauses, et la troisième est celle qu'on oublie : c'est elle qui rend la comparaison au dernier licite. Variant : n − i. Conclusion : à i = n, la tranche vaut l'entrée entière, donc merged est exactement la fusion de tous.
« merged est exactement la fusion des i premiers, disjoints et rangés, donc le seul fusionné que le suivant peut atteindre est celui qui finit le plus tard, donc le traiter préserve les trois clauses, donc à la dernière lecture merged est exactement la fusion de tous les intervalles. »
- i = 0,
[1,3].mergedvide → on ouvre.merged = [[1,3]], frontière 3. Exactement la fusion de[[1,3]]. ✔ - i = 1,
[2,6]. 2 ≤ 3 → prolonge, fin = max(3, 6) = 6.merged = [[1,6]]. Un seul bloc : les deux se recouvrent sur [2, 3]. - i = 2,
[8,10]. 8 > 6 → ouvre.merged = [[1,6],[8,10]], frontière 10. Disjoints et triés. ✔ - i = 3,
[9,12]. 9 ≤ 10 → prolonge, fin = max(10, 12) = 12.merged = [[1,6],[8,12]]. Le[1,6]n'a même pas été regardé — et c'est exactement ce que la troisième clause autorise. - i = 4,
[15,18]. 15 > 12 → ouvre.merged = [[1,6],[8,12],[15,18]]. - Conclusion. Variant nul donc la tranche vaut
intervalstout entier doncmergedest exactement la fusion des cinq. Couverture 5 + 4 + 3 = 12, contre 14 en sommant les longueurs brutes.
Vérifié à l'exécution. La sortie confrontée à l'union calculée point par point, sur 200 000 tirages de 1 à 6 intervalles entiers : 0 désaccord, et 0 sortie dont deux intervalles consécutifs se chevauchent. Les deux tests comptent — le premier dit « rien n'est perdu », le second dit « rien n'est en double ».
Le coût : une somme que le tri domine
Deux phases, additionnées et non multipliées. Le tri est en O(n log n), le balayage fait exactement un test par intervalle sauf le premier, donc O(n). La somme est écrasée par le premier terme.
La phrase qui rapporte des points : si l'entrée arrive déjà triée — un journal, un index, une table SQL avec ORDER BY — le coût tombe à O(n). Le tri n'est pas dans le problème, il est dans la préparation.
« Le balayage fait un test par intervalle, donc il est linéaire, donc le seul terme qui dépasse est celui du tri, donc le total est n log n — et si l'entrée arrive triée, le tri est déjà payé et je descends en linéaire. »
Les deux phases, séparément. n = 100 000 intervalles aléatoires, comparaisons instrumentées :
- le tri : 1 531 888 comparaisons, soit 0,92 × n log₂ n (Timsort fait un peu mieux que la borne) ;
- le balayage : 99 999 tests
s <= fin, soit exactement n − 1 ; - rapport 15×. Le balayage est un arrondi dans la facture du tri.
Chronométré, n = 106. Tri 1,20 s · balayage 0,81 s — soit à peine 1,5×, alors que les comparaisons disent 15×. La raison est prosaïque et se dit : sorted() est écrit en C, la boucle de fusion est écrite en Python. L'asymptotique dit le tri, la montre dit presque l'égalité ; l'entretien attend l'asymptotique, mais savoir que l'écart existe évite de promettre un gain qu'on ne mesurera pas.
Combien reste-t-il en sortie ? 1 000 intervalles de longueur 20 tirés sur un axe de plus en plus large : sur [0, 2 000] il ne reste 1 intervalle (tout se recouvre), sur [0, 20 000] il en reste 351, sur [0, 200 000] il en reste 904. La sortie est O(n) au pire, et l'espace se majore par là — jamais par le nombre de fusions, qu'on ne contrôle pas.
Les variantes : même axe, autre chose à retenir
La charpente ne bouge pas — trier des bornes, balayer une fois. Ce qui change est ce qu'on retient en chemin. Insérer (LC 57) : trois phases, avant / chevauchement / après, sur une entrée déjà fusionnée. Salles (LC 253) : des événements +1 à chaque début, −1 à chaque fin, et le maximum du compteur.
LC 435 est le seul de la famille à trier par fin : un glouton qui garde ce qui libère l'axe le plus tôt. Savoir dire lequel et pourquoi vaut plus que savoir les coder.
« La charpente est un balayage sur des bornes ordonnées, donc changer de question revient à changer ce qu'on retient en chemin, donc les salles se comptent sur un compteur d'événements et le retrait minimal se décide sur la fin la plus tôt, donc c'est le même tri qui porte les trois. »
LC 57 — insérer [4,9] dans [[1,6],[8,12],[15,18]] (la sortie du fil rouge, donc déjà fusionnée) :
[1,6] finit en 6, il touche déjà le nouveau[1,6] et [8,12] : début = min(4, 1) = 1, fin = max(9, 12) = 12[15,18]résultat [[1, 12], [15, 18]] — un seul intervalle en absorbe deux, en O(n) : l'entrée était déjà triée, il n'y a rien à trier.
LC 253 — salles pour [[0,30],[5,10],[15,20]]. Six événements, triés par instant : 2 salles. Trois méthodes donnent le même chiffre, et il faut savoir les nommer : compteur d'événements ±1 · débuts et fins triés séparément avec deux pointeurs · min-heap des fins (c07, pas 2), dont la racine est encore un seuil. Vérifié sur 100 000 tirages : 0 désaccord entre le compteur et le tas.
LC 435 — et le piège du tri. Sur [[1,100],[2,3],[4,5],[6,7]], trier par fin retire 1 intervalle (on jette [1,100]) ; trier par début en retire 3 (on garde le monstre et on jette les trois petits). Trois fois pire, et aucune erreur levée.
Les trois réunions en haut ; en bas, le compteur : +1 à chaque début, −1 à chaque fin, événements pris dans l'ordre des instants. Les barres passent au rouge tant qu'elles sont ouvertes à l'instant courant : leur nombre est le compteur, on peut les recompter à l'œil. Fais « pas › » six fois et lis l'escalier : il monte à 2, redescend, remonte à 2, et le trait rouge horizontal retient le maximum — c'est la réponse, 2 salles. Ce que la figure montre et qu'une liste ne montrerait pas : [0,30] est seule à couvrir tout l'axe, et pourtant elle ne coûte qu'une salle ; ce qui coûte, ce n'est pas la durée, c'est la simultanéité. Et remarque qu'ici on a cassé les paires : les débuts et les fins sont triés séparément, on ne sait même plus quelle fin appartient à quelle réunion — et on n'en a pas besoin. C'est la différence exacte avec la fusion du pas 2, où l'intervalle reste entier d'un bout à l'autre.
Où ça casse casse
Le balayage ne consulte que merged[-1]. Cette économie est gagée sur le tri par début : sans lui, ou trié par fin, un intervalle peut chevaucher un fusionné antérieur au dernier — et ce chevauchement n'est jamais testé.
Rien ne plante, rien ne ralentit : la fonction rend une liste d'intervalles parfaitement bien formée, et fausse. C'est le contre-signal à savoir construire, parce qu'aucun test aléatoire ne le trouve de façon fiable.
« Le balayage ne consulte que le dernier fusionné, donc sans tri par début un chevauchement avec un fusionné antérieur n'est jamais testé, donc la sortie peut contenir deux intervalles qui se recouvrent ou perdre une plage entière, donc la réponse est fausse et rien ne l'a signalé. »
Trié par fin au lieu de début. [[1,10],[2,3],[4,5]]. Par début : un seul bloc, [[1, 10]] — juste. Trié par fin l'ordre devient [2,3], [4,5], [1,10], et le balayage rend [[2, 3], [4, 10]]. Deux intervalles au lieu d'un, et les plages [1, 2] et [3, 4] ont disparu de la sortie alors qu'elles sont couvertes par [1,10]. Le [2,3], lui, n'a jamais été relu : il n'était pas le dernier.
Pas de tri du tout. [[1,3],[8,10],[2,6]] → [[1, 3], [8, 10]]. L'intervalle [2,6] a été absorbé par [8,10] (2 ≤ 10, fin = max(10, 6) = 10) : il s'est évaporé sans laisser de trace, et la plage [3, 6] avec lui. La sortie est plus courte que l'entrée, ce qui a toutes les apparences d'une fusion réussie.
Et le symétrique, pour LC 435. Là c'est trier par début qui casse : sur [[1,100],[2,3],[4,5],[6,7]] le glouton par début garde [1,100] et retire 3 intervalles au lieu de 1. Il rend un entier plausible, positif, et faux.
La phrase qui tue. « Je trie par début pour fusionner, par fin pour un glouton de retrait — et si je me trompe de borne, je n'obtiens pas une erreur, j'obtiens une mauvaise réponse. »
<au lieu de<=sur des intervalles jointifs.[[1,3],[3,5]]donne [[1, 5]] avec<=et [[1, 3], [3, 5]] avec<— vérifié. Aucune des deux n'est « la bonne » : c'est l'énoncé qui tranche, et la question se pose à voix haute avant d'écrire la ligne.- Muter l'entrée en croyant travailler sur une copie.
merged.append(x)range la référence, et lemerged[-1][1] = …suivant écrit dans la liste de l'appelant : partant de[[1,3],[2,6]], l'entrée vaut[[1,6],[2,6]]à la sortie — vérifié. Remède :append(list(x)), ou des tuples en entrée, qui rendent la faute impossible. - Les égalités d'instants, pour les salles. Sur
[[0,10],[10,20]]: fin avant début à instant égal donne 1 salle (elle se libère et se reprend), début avant fin en donne 2. Les deux conventions divergent sur 27,5 % des tirages aléatoires (100 000 essais) : ce n'est pas un cas limite exotique, c'est plus d'un cas sur quatre. sorted(intervals)trie par début puis par fin, lexicographiquement :[[1,9],[1,2],[0,5]]devient[[0,5],[1,2],[1,9]]. C'est suffisant pour la fusion — à début égal, l'ordre des fins ne change pas le résultat, lemaxs'en charge — mais ça se dit, plutôt que de laisser croire qu'on n'y a pas pensé.
Résumé
- Signal : des segments [début, fin] d'un même axe et une question de recouvrement — fusion, insertion, salles, couverture. Contre-signal : cercle ou 2D.
- Le pattern : trier par début, balayer, ne comparer qu'au dernier fusionné — prolonger avec
fin = max(fin, e), ou ouvrir. Lemaxest obligatoire : un intervalle inclus ferait reculer la fin. - Pourquoi le dernier suffit : les débuts sont croissants, donc un intervalle à venir ne peut atteindre aucun fusionné antérieur. C'est le tri qui l'achète, et c'est ça qu'on dit.
- Invariant :
merged= exactement la fusion deintervals[0:i), disjoints, triés, etmerged[−1]finit le plus tard. Variant : n − i. - Coût : O(n log n) — une somme dominée par le tri (15× le balayage en comparaisons). Entrée déjà triée ⇒ O(n). Espace O(n) de sortie, O(1) en plus.
- Variantes : insérer = trois phases · salles = événements ±1 et maximum du compteur, ou min-heap des fins · retrait minimal = trier par fin, glouton.
- Où ça casse : mauvais tri ⇒ chevauchement avec un fusionné antérieur jamais testé.
[[1,10],[2,3],[4,5]]trié par fin rend[[2,3],[4,10]]au lieu de[[1,10]]— sans erreur.
Chaîne verbalisée — une prise, à voix haute
- Pourquoi trier par début suffit-il à ne comparer qu'au dernier fusionné ?Parce qu'après le tri les débuts sont croissants : l'intervalle courant commence après tous les débuts déjà lus, donc après le début du dernier fusionné, donc a fortiori après la fin de tous les fusionnés antérieurs — qui sont disjoints et rangés avant lui. Aucun d'eux n'est atteignable, la comparaison au seul dernier est donc complète. C'est le tri qui achète cette impossibilité ; sans lui l'économie est fausse.
- L'invariant, et le variant ?Après avoir traité intervals[0:i), merged est exactement la fusion de ces i intervalles : deux à deux disjoints, triés par début, et merged[−1] est celui qui finit le plus tard. Les trois clauses servent, et la troisième est celle qu'on oublie — c'est elle qui rend licite de ne regarder que le dernier. Variant : n − i. Conclusion : à i = n la tranche vaut l'entrée entière, donc merged est la fusion de tout.
- La complexité, et l'exception qui rapporte des points ?Une somme : O(n log n) pour le tri plus O(n) pour le balayage, qui fait exactement un test par intervalle. Le total est n log n. L'exception : si l'entrée arrive déjà triée — un journal, un ORDER BY, la sortie d'une fusion précédente — on descend à O(n). Espace O(n) pour la sortie, O(1) en plus. Mesuré à n = 100 000 : 1,53 million de comparaisons pour le tri contre 99 999 tests pour le balayage, soit 15×.
- Salles de réunion : deux méthodes, et quand trier par fin ?Salles : soit un compteur d'événements, +1 à chaque début et −1 à chaque fin, événements triés par instant, et on prend le maximum du compteur ; soit les débuts et les fins triés séparément avec deux pointeurs ; soit un min-heap des fins courantes, dont la taille finale est la réponse. Trier par fin, c'est pour LC 435, le retrait minimal : glouton qui garde à chaque fois l'intervalle qui libère l'axe le plus tôt. C'est le seul de la famille à trier par fin.
- Qu'est-ce qui casse sans lever d'erreur ?Le mauvais tri. Sur [[1,10],[2,3],[4,5]], trié par fin, le balayage rend [[2,3],[4,10]] au lieu de [[1,10]] : le [2,3] n'est jamais relu puisqu'il n'est plus le dernier, et les plages [1,2] et [3,4] disparaissent. Sans tri du tout, [[1,3],[8,10],[2,6]] rend [[1,3],[8,10]] — le [2,6] est absorbé par [8,10] et s'évapore. Dans les deux cas la sortie est une liste d'intervalles bien formée, plus courte que l'entrée, et fausse.
Ponts et cartes
v > h[0] retourné
c00 · L'invariantle conteneur est ici la liste de sortie et non un scalaire : « merged = exactement la fusion de intervals[0:i) » est le même rituel, avec un objet plus gros et une clause de plus
c00 · La complexité composéele cas somme et non produit : tri + balayage, et un terme écrase l'autre. C'est là que se dit l'exception « entrée déjà triée ⇒ O(n) », qui n'existe pas dans un coût multiplicatif
c01 · Fenêtre glissantel'autre balayage à mémoire bornée : là on retient deux indices d'une tranche contiguë, ici un seul nombre — la fin du dernier fusionné. Même économie, et dans les deux cas c'est une monotonie qui la justifie
c09 · DP 1Dla suite : quand ce qu'on retient d'une position ne se résume plus à une borne mais à la valeur d'un sous-problème, le balayage devient une récurrence
coding::intervals (le squelette de LC 56, fin = max(fin, e), l'invariant à trois clauses, les trois phases de LC 57) · coding::balayage (les événements ±1 de LC 253, le maximum du compteur, le min-heap des fins, la convention d'égalité d'instants) · coding::tri (trier par début pour fusionner, par fin pour le glouton de LC 435 ; ce que chaque tri achète, et ce qui casse silencieusement quand on se trompe).
Une carte qui résiste après cette chaîne est une carte à refondre, pas une section à relire.