Probleme – La droite de balayage

1. Le naïf. Le maximum est atteint en un point qui est le début de l'un des intervalles — car la fonction de recouvrement ne peut croître qu'en un début. On teste donc, pour chacun des $n$ débuts, combien d'intervalles le contiennent : $\Theta (n^2)$.

2. Le balayage. On ne regarde plus les intervalles, mais les événements : $+1$ à chaque ouverture, $-1$ à chaque fermeture. On les trie par abscisse et on les parcourt en tenant un compteur.

(* Nombre maximal d'intervalles [d, f[ simultanément ouverts.
   Précondition : d < f pour chaque intervalle. Complexité : Theta(n log n). *)
let recouvrement iv =
  let n = Array.length iv in
  let ev = Array.make (2 * n) (0, 0) in
  Array.iteri (fun i (d, f) -> ev.(2*i) <- (d, 1); ev.(2*i+1) <- (f, -1)) iv;
  (* à égalité d'abscisse, les FERMETURES (-1) passent avant les ouvertures (+1) *)
  Array.sort (fun (a, sa) (b, sb) ->
    if a <> b then compare a b else compare sa sb) ev;
  let ouverts = ref 0 and record = ref 0 in
  (* INVARIANT : après avoir traité les événements d'abscisse <= x, ouverts est
     le nombre d'intervalles contenant x, et record leur maximum sur ]-inf, x]. *)
  Array.iter (fun (_, s) ->
    ouverts := !ouverts + s;
    if !ouverts > !record then record := !ouverts) ev;
  !record

Terminaison : la boucle parcourt un tableau de $2n$ cases. Correction : l'invariant est immédiat par récurrence sur les événements traités, et le maximum du recouvrement est atteint juste après une ouverture — donc examiné.

3. Les égalités, et c'est là qu'est la faute. L'intervalle est semi-ouvert : $[1,3[$ et $[3,5[$ ne se rencontrent pas. Si l'ouverture de $[3,5[$ était traitée avant la fermeture de $[1,3[$, le compteur passerait fugitivement à $2$ et l'algorithme rendrait $2$ au lieu de $1$. L'ordre des événements de même abscisse fait partie de la spécification, et il se règle en une ligne : compare sa sb met $-1$ avant $+1$.

Si les intervalles étaient fermés, $[1,3]$ et $[3,5]$ se rencontreraient en $3$, et il faudrait l'ordre inverse. Deux lignes de code qui diffèrent d'un signe, pour deux problèmes différents.

4. La mesure, les deux méthodes ayant été confrontées sur $2000$ instances aléatoires sans un seul désaccord :

Le rapport vaut $n/2$ : c'est le passage de $\Theta (n^2)$ à $\Theta (n)$ après le tri.

Ce que le balayage change vraiment. Il ne s'agit pas d'une astuce d'implémentation : c'est un changement d'objet. On cesse de raisonner sur les intervalles, qui sont des objets à deux extrémités et se comparent mal, pour raisonner sur les instants où quelque chose se produit — objets ponctuels, totalement ordonnés, donc triables. La même transformation résoudra la sélection d'activités au chapitre chap:gloutons et l'intersection de segments dans tout logiciel de géométrie.