Nombre minimal de salles

Le nombre minimal de salles égale le nombre maximal d'activités simultanées. On trie séparément les débuts et les fins (tri_fusion du chapitre 9 sur des entiers) et l'on balaie le temps :

let salles activites =
  let debuts = tri_fusion (List.map (fun a -> a.debut) activites) in
  let fins = tri_fusion (List.map (fun a -> a.fin) activites) in
  let rec balayage debuts fins courant maxi =
    match debuts, fins with
    | [], _ -> maxi
    | d :: rd, f :: rf ->
        if d < f then
          let c = courant + 1 in
          balayage rd fins c (if c > maxi then c else maxi)
        else
          balayage debuts rf (courant - 1) maxi
    | _ -> maxi
  in
  balayage debuts fins 0 0

On avance dans le temps : un début avant la prochaine fin fait monter le nombre d'activités en cours (courant) — on note le pic maxi ; une fin le fait baisser. Le pic est le nombre de salles nécessaires. (d < f : une activité qui finit pile quand une autre commence libère la salle à temps.)