Problème — Optimisation du temps de salle

On applique le glouton de sélection d'activités (tri par fin), puis on calcule les durées.

def planning_salle(reunions):
    reunions = sorted(reunions, key=lambda r: r[1])
    retenues = []
    fin_courante = float("-inf")
    for debut, fin in reunions:
        if debut >= fin_courante:
            retenues.append((debut, fin))
            fin_courante = fin
    if not retenues:
        return [], 0.0
    duree_occupee = sum(fin - debut for debut, fin in retenues)
    amplitude = retenues[-1][1] - retenues[0][0]
    taux = duree_occupee / amplitude
    return retenues, taux

demandes = [(9, 11), (10, 12), (11, 13), (13, 14), (12, 15)]
planning, taux = planning_salle(demandes)
print(planning)            # [(9, 11), (11, 13), (13, 14)]
print(round(taux, 2))      # 1.0

Le glouton sélectionne $(9,11)$, $(11,13)$, $(13,14)$ : trois réunions enchaînées sans temps mort, d'où un taux d'occupation de $1,0$. La complexité reste $O(n\log n)$.