Problème — Optimisation du temps de salle

Les algorithmes gloutons · niveau 2

Énoncé

Problème — Optimisation du temps de salle.

Une salle de conférence reçoit des demandes de réservation, chacune avec une heure de début et de fin. On veut accepter le maximum de réunions sans chevauchement, puis afficher le planning retenu et le taux d'occupation (durée totale occupée sur l'amplitude totale).

Corrigé

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 lo g n)$ .