Algorithmes gloutons

Un problème d'optimisation combinatoire est la donnée d'un ensemble fini de candidats, d'un ensemble $\mathcal{R}$ de solutions réalisables, celles qui respectent les contraintes, le plus souvent un ensemble de parties de l'ensemble des candidats, parfois un ensemble de vecteurs comme au sac à dos fractionnaire, et d'une fonction objectif $v : \mathcal{R} \to \mathbb{R}$. Le résoudre, c'est exhiber une solution réalisable $S^\star$ telle que, pour toute solution réalisable $S$, $v(S) \leq v(S^\star)$ s'il s'agit de maximiser, ou $v(S) \geq v(S^\star)$ s'il s'agit de minimiser ; une telle solution est dite optimale. Dans les problèmes de cette fiche, l'ensemble $\mathcal{R}$ est fini, sauf pour le sac à dos fractionnaire, où il est une partie fermée bornée de $\mathbb{R}^n$ sur laquelle l'objectif, continu, atteint son maximum : dès qu'il est non vide, une solution optimale existe. Encore faut-il qu'il le soit, et cela ne va pas de soi : pour le rendu de monnaie, c'est la présence de la pièce de $1$ qui l'assure, et le système $(6, 4)$ ne rend pas le montant $3$. L'existence une fois acquise, ce qui est en jeu n'est plus elle, mais le calcul de l'optimum : énumérer $\mathcal{R}$ coûte en général un temps exponentiel.

Un algorithme glouton construit une solution par une suite de choix définitifs : les candidats sont examinés dans un ordre fixé une fois pour toutes par un critère glouton, et chacun est ajouté à la solution partielle dès que cet ajout la laisse réalisable. Aucun choix n'est jamais remis en cause : ni retour en arrière, ni exploration de plusieurs branches (voir le thème Récursivité et diviser pour régner). Le schéma tient en six lignes, où cle donne l'ordre d'examen et realisable teste la contrainte.

def glouton(candidats, cle, realisable):
    """candidats : les objets parmi lesquels choisir.
       cle : fonction de tri, le meilleur candidat en premier.
       realisable : fonction (solution, candidat) -> booleen.
       Renvoie la solution construite par choix successifs, sans retour en arriere."""
    solution = []
    for candidat in sorted(candidats, key=cle):
        if realisable(solution, candidat):
            solution.append(candidat)
    return solution

Un glouton est donc entièrement déterminé par deux décisions : quel critère de tri et quel test de faisabilité. Changer le critère change l'algorithme, et le plus souvent son optimalité.

Un candidat est un objet parmi lesquels l'algorithme choisit : une pièce, une activité, un objet du sac. Le critère glouton est la règle de tri qui fixe l'ordre d'examen, et la solution partielle est ce qui est déjà construit au cours de la boucle. Une solution est réalisable (ou admissible) quand elle respecte les contraintes, optimale quand aucune réalisable ne fait mieux. Un algorithme qui renvoie une solution réalisable sans garantie d'optimalité est une heuristique ; le rapport d'approximation est alors le quotient de sa valeur par l'optimum. Un argument d'échange est la démonstration qui transforme une solution optimale en une solution optimale contenant le choix glouton. Un système de pièces est canonique quand le glouton y est optimal pour tout montant. Une borne inférieure est une minoration de l'optimum valable pour toute solution réalisable, indépendamment de l'algorithme.

Propriété : si l'ensemble des candidats est fini, si la solution vide est réalisable et si le test de faisabilité est correct, alors l'algorithme glouton termine et renvoie une solution réalisable. La démonstration tient en deux lignes : la boucle for fait exactement un tour par candidat, donc elle termine ; et « la solution partielle est réalisable » est un invariant, vrai au départ puisque la solution vide l'est, conservé par chaque tour puisqu'un candidat n'est ajouté qu'après le test (voir le thème Algorithmes élémentaires et preuve de programmes pour les invariants).
En revanche, rien ici n'assure l'optimalité. Un glouton est par défaut une heuristique : son optimalité est un théorème à démontrer problème par problème, ou à réfuter par un contre-exemple. Ainsi, sur le système de pièces $(4, 3, 1)$ et le montant $6$, le glouton rend $4 + 1 + 1$, soit trois pièces, alors que $3 + 3$ en demande deux.

Pour $n$ candidats, le schéma glouton effectue un tri puis $n$ tests de faisabilité. Le tri de Python coûte $O(n \log n)$ comparaisons (voir le thème Python : listes, tuples, chaînes et dictionnaires), donc si chaque test coûte $O(1)$, le coût total est $O(n \log n)$ : le tri domine. Rappel du bloc Analyse 2 : $f = O(g)$ signifie qu'il existe une constante $C > 0$ et un rang au-delà duquel $|f| \leq C |g|$, et $f = \Theta(g)$ que l'on a à la fois $f = O(g)$ et $g = O(f)$. Un $O$ majore, un $\Theta$ situe : un coût en $\Theta(n \log n)$ est aussi un $O(n^2)$, et l'écrire ainsi n'est pas faux, seulement moins précis. Si l'énoncé fournit déjà les candidats dans le bon ordre, le coût tombe à $O(n)$ ; si le test de faisabilité parcourt toute la solution partielle, il remonte à $O(n^2)$ ; si l'état est maintenu dans un tas, chaque tour coûte $O(\log n)$ et le total reste $O(n \log n)$. C'est là tout l'intérêt pratique des gloutons : quasi-linéaires, là où l'énumération des solutions est exponentielle.

Quand l'utiliser : l'énoncé demande de construire une solution « le plus tôt possible », « en le moins de », « en le plus de », et un ordre naturel se devine sur les données (la plus grande pièce, la première date de fin, la meilleure valeur massique).
1) Écrire la spécification avant le code, en docstring : ce que reçoit la fonction (types et contraintes sur les données : entiers strictement positifs, liste déjà triée), ce qu'elle renvoie (l'objet exact, et ce qu'elle renvoie quand il n'y a pas de solution), et ce qu'elle ne fait pas (elle ne modifie pas la liste reçue). Voir le thème Python : structures de contrôle et fonctions.
2) Nommer le critère glouton en français, puis le traduire en clé de tri : « par date de fin croissante » devient sorted(activites, key=lambda activite: activite[1]). Toujours sorted, jamais .sort() sur la liste de l'appelant.
3) Initialiser la solution vide et les variables d'état qui résument les choix déjà faits : le reste à rendre, la date de fin courante, la capacité restante.
4) Une boucle for sur les candidats triés, un test de faisabilité qui n'utilise que l'état, une mise à jour de l'état. Pas de break qui saute la mise à jour.
5) Écrire l'invariant sous la boucle, en une phrase qui relie l'état et la solution partielle aux données (« ce qui est rendu plus ce qui reste fait le montant »), puis dire ce qu'il donne à la sortie. Pour une boucle while, écrire aussi le variant, un entier naturel qui décroît strictement.
6) Tester quatre cas : liste vide, un seul candidat, candidats de même clé, et le cas limite de l'énoncé (montant nul, capacité nulle).

Un système de pièces est une liste finie d'entiers strictement positifs $c_1 > c_2 > \dots > c_k$, les valeurs disponibles, chacune en quantité illimitée. Rendre le montant $n \in \mathbb{N}$, c'est trouver des entiers naturels $x_1, \dots, x_k$ tels que $\sum_{i=1}^{k} x_i c_i = n$ ; le rendu minimal est celui qui minimise le nombre de pièces $\sum_{i=1}^{k} x_i$. Le rendu glouton sert d'abord la plus grande valeur possible : $x_1 = \lfloor n / c_1 \rfloor$, puis recommence sur le reste $n - x_1 c_1$. On travaille toujours en centimes, donc sur des entiers.

Le système de pièces est donné par la liste pieces de ses valeurs, entières, strictement positives et rangées par ordre décroissant. Écrire une fonction qui rend un montant entier n par la méthode gloutonne, démontrer sa terminaison, établir un invariant de boucle, en déduire sa correction et donner son coût.
Spécification et programme.

def rendu_glouton(pieces, n):
    """pieces : valeurs entieres strictement positives, rangees par ordre decroissant.
       n : entier naturel.
       Renvoie la liste des pieces rendues, de la plus grande a la plus petite,
       ou None si le glouton n'arrive pas a completer le montant."""
    rendu = []
    reste = n
    for valeur in pieces:
        nombre = reste // valeur
        rendu += [valeur] * nombre
        reste -= nombre * valeur
    return rendu if reste == 0 else None

Terminaison. La boucle for parcourt la liste pieces, de longueur finie $k$ : elle effectue exactement $k$ tours, et chaque tour est une division euclidienne suivie de deux affectations. La fonction termine donc.
Invariant. Notons $R$ le contenu de rendu et $r$ celui de reste au début du tour d'indice $j$, et montrons par récurrence sur $j$ que $\sum_{p \in R} p + r = n$ et $r \geq 0$.
Avant le premier tour, $R$ est vide et $r = n$ : la somme vaut $0 + n = n$, et $r = n \geq 0$.
Supposons l'invariant vrai au début d'un tour, de valeur $c$. Le tour calcule $q = \lfloor r / c \rfloor$, ajoute $q$ pièces de valeur $c$ à $R$ et remplace $r$ par $r - qc$. La somme des pièces augmente donc de $qc$ et le reste diminue de $qc$ : leur somme est inchangée et vaut encore $n$. De plus $r - qc$ est le reste de la division euclidienne de $r$ par $c$, donc $0 \leq r - qc < c$ : l'invariant est vrai au début du tour suivant, et l'on retiendra au passage qu'à la fin du tour de la valeur $c$, le reste est strictement inférieur à $c$.
Correction. À la sortie, l'invariant donne $\sum_{p \in R} p + r = n$. Si $r = 0$, la liste renvoyée est bien un rendu du montant $n$. Si de plus la plus petite valeur du système est $1$, alors après le dernier tour on a $0 \leq r < 1$, donc $r = 0$ : le glouton aboutit toujours, et la fonction ne renvoie jamais None.
Coût. Le tour de la valeur $c$ effectue une division euclidienne, en $O(1)$, et l'écriture de $q$ pièces, en $O(q)$. En notant $N$ le nombre total de pièces rendues, le coût est donc $O(k + N)$.
Vérification. L'appel rendu_glouton([200, 100, 50, 20, 10, 5, 2, 1], 289) renvoie [200, 50, 20, 10, 5, 2, 2], soit sept pièces, de somme $289$.
À retenir : la spécification, écrite avant le code, fixe ce que signifie None ; l'invariant « ce qui est rendu plus ce qui reste fait le montant » est ce qui rend la fonction juste, et c'est la présence de la pièce de $1$, et elle seule, qui garantit qu'elle aboutit.

Ligne fautive : rendu_glouton([2.0, 1.0, 0.5, 0.2, 0.1], 2.9).
Premier symptôme, une erreur : reste // valeur vaut ici un flottant, et l'interpréteur refuse [valeur] * nombre avec TypeError: can't multiply sequence by non-int of type 'float'.
Deuxième symptôme, plus grave, une fois l'erreur corrigée par int(reste // valeur) : le montant $2{,}9$ n'a pas d'écriture binaire exacte. Le reste vaut $0{,}8999999999999999$ après la pièce de $2$, puis $0{,}3999999999999999$ après celle de $0{,}5$ ; le quotient de ce reste par $0{,}2$ vaut alors $1$ au lieu de $2$, et la fonction s'achève sur un reste de $0{,}0999999999999999$, non nul : elle renvoie None alors que $2{,}9 = 2 + 0{,}5 + 0{,}2 + 0{,}2$. Le même phénomène se lit sur 0.1 + 0.2 == 0.3, qui vaut False.
Version correcte : travailler en centimes, donc sur des entiers, pour lesquels //, % et == sont exacts. rendu_glouton([200, 100, 50, 20, 10], 290) renvoie [200, 50, 20, 20]. Si l'énoncé impose des décimaux, utiliser Fraction du module fractions (voir le thème Python : types, variables et expressions), et ne jamais tester reste == 0 sur des flottants.

Phrase fautive : « le glouton descend les valeurs une à une, donc il finit forcément par rendre le montant ».
C'est faux dès que la pièce de $1$ manque. Sur le système $(5, 3)$ et le montant $9$, le glouton rend une pièce de $5$, il reste $4$ ; il rend une pièce de $3$, il reste $1$ ; aucune valeur ne convient plus, et la fonction renvoie None. Or $9 = 3 + 3 + 3$ est un rendu parfaitement valide, en trois pièces. L'échec du glouton ne démontre donc pas l'inexistence d'un rendu.
Version correcte : la spécification annonce None comme « le glouton n'aboutit pas », et non « il n'existe pas de rendu ». Pour savoir s'il existe un rendu, et combien de pièces il demande, on calcule l'optimum exact (voir la méthode « Éprouver un glouton en le confrontant à l'optimum exact »). Quand la plus petite valeur du système vaut $1$, la question ne se pose pas : le glouton aboutit toujours, comme le montre la rédaction modèle du rendu de monnaie.

Deux propriétés fondent toute preuve d'optimalité d'un glouton. La propriété du choix glouton : il existe une solution optimale qui contient le premier choix de l'algorithme. La sous-structure optimale : une fois ce premier choix fait, ce qui reste d'une telle solution optimale est une solution optimale du sous-problème, celui qu'on obtient en retirant ce choix et les candidats devenus irréalisables. Réunies, elles donnent l'optimalité par récurrence sur le nombre de candidats (voir le thème Récurrence simple du bloc Fondamental). C'est cette structure en deux temps qu'il faut retrouver dans chaque preuve, et c'est l'une des deux qui manque lorsqu'un glouton échoue.

Propriété : soit $g$ le premier candidat choisi par le glouton et soit $S$ une solution optimale. Si l'on sait construire à partir de $S$ une solution réalisable $S'$ qui contient $g$ et vérifie $v(S') \geq v(S)$ pour une maximisation (ou $v(S') \leq v(S)$ pour une minimisation), alors $S'$ est optimale et contient $g$ : la propriété du choix glouton est établie. La construction s'appelle un échange : on retire de $S$ l'élément que le critère glouton désigne, c'est-à-dire celui qui ressemble le plus à $g$, et l'on met $g$ à sa place. Deux vérifications, jamais une seule : que $S'$ reste réalisable, ce qui utilise exactement la propriété qui définit le critère, et que sa valeur ne baisse pas.

Quand l'utiliser : l'énoncé demande de « démontrer que l'algorithme renvoie une solution optimale », ou de « justifier le choix du critère ».
1) Poser les notations : une instance $I$ à $n$ candidats, $G(I)$ la solution renvoyée par le glouton, $S$ une solution optimale, dont on rappelle en une phrase qu'elle existe (les solutions réalisables sont en nombre fini et il y en a au moins une, ou bien elles forment un compact non vide sur lequel l'objectif est continu). Annoncer une récurrence forte sur $n$.
2) Traiter le cas de base : $n = 0$, ou l'instance sans candidat réalisable. Les deux solutions sont vides, le résultat est acquis.
3) Faire l'échange. Soit $g$ le premier choix du glouton. Si $g \in S$, poser $S' = S$. Sinon, désigner dans $S$ l'élément $s$ que le critère place en tête, poser $S' = (S \setminus \{s\}) \cup \{g\}$, puis écrire les deux vérifications : $S'$ est réalisable (c'est ici, et seulement ici, que sert la propriété qui définit le critère glouton), et $v(S') \geq v(S)$, donc $S'$ est optimale.
4) Isoler le sous-problème $I'$ : les candidats qui restent réalisables une fois $g$ choisi. Montrer que $S' \setminus \{g\}$ est optimale pour $I'$, par l'absurde : une meilleure solution de $I'$, augmentée de $g$, battrait $S'$.
5) Vérifier que le glouton, après avoir choisi $g$, se comporte exactement comme le glouton lancé sur $I'$ : même ordre d'examen, mêmes tests, et les candidats de $I \setminus I'$ sont rejetés. Cette ligne est souvent oubliée et c'est elle qui autorise la récurrence.
6) Appliquer l'hypothèse de récurrence à $I'$, qui a strictement moins de candidats, et conclure : $|G(I)| = 1 + |G(I')| = 1 + (|S'| - 1) = |S'| = |S|$, donc $G(I)$ est optimale.
7) Ne jamais écrire « le glouton fait le meilleur choix à chaque étape, donc il est optimal » : c'est précisément ce qu'il faut démontrer, et c'est faux en général.

Une activité est un couple d'entiers $(d, f)$ avec $d < f$ : elle occupe l'intervalle $[d, f[$. Deux activités $(d_1, f_1)$ et $(d_2, f_2)$ sont compatibles lorsque $f_1 \leq d_2$ ou $f_2 \leq d_1$, autrement dit lorsque leurs intervalles sont disjoints. Le problème de la sélection d'activités : étant données $n$ activités et une seule salle, en retenir un nombre maximal, deux à deux compatibles. Le critère glouton est la date de fin croissante : on retient à chaque fois l'activité qui libère la salle le plus tôt, puisque c'est elle qui laisse le plus de place aux suivantes.

Théorème : soit une famille finie d'activités ; l'algorithme qui les examine par date de fin croissante et retient celles qui sont compatibles avec la dernière retenue renvoie une famille d'activités deux à deux compatibles de cardinal maximal. La démonstration est exigible : elle se fait par échange, et la rédaction modèle qui suit l'écrit en entier. Attention à ce qui est optimisé : le nombre d'activités, et non la durée totale occupée, ni la satisfaction d'un demandeur particulier, ni une quelconque pondération des activités. Le résultat tombe si l'on remplace le critère par la durée croissante ou par la date de début croissante (voir le piège correspondant), et il tombe aussi si les activités portent des poids que l'on cherche à maximiser.

Les activités sont des couples d'entiers (debut, fin) avec debut < fin. Écrire une fonction qui en renvoie une famille de cardinal maximal, deux à deux compatibles, puis démontrer son optimalité.
Pour une activité $a$, on note $d(a)$ sa date de début et $f(a)$ sa date de fin.

def selection_activites(activites):
    """activites : liste de couples (debut, fin) d'entiers avec debut < fin.
       Renvoie une liste de cardinal maximal d'activites deux a deux compatibles,
       rangee par date de fin croissante. La liste recue n'est pas modifiee."""
    choisies = []
    fin_courante = None
    for debut, fin in sorted(activites, key=lambda activite: activite[1]):
        if fin_courante is None or debut >= fin_courante:
            choisies.append((debut, fin))
            fin_courante = fin
    return choisies

Sur l'exemple [(0, 6), (1, 4), (3, 5), (5, 7), (5, 9), (8, 9)], la fonction renvoie [(1, 4), (5, 7), (8, 9)].
La famille renvoyée est compatible. Les activités sont examinées par dates de fin croissantes, donc les dates de fin des activités retenues sont croissantes et la variable fin_courante contient la plus grande d'entre elles. Quand une activité $a$ est ajoutée, son début est supérieur ou égal à cette valeur, elle-même supérieure ou égale à $f(c)$ pour toute activité $c$ déjà retenue : ainsi $f(c) \leq d(a)$, et $a$ est compatible avec chacune d'elles.
Montrons l'optimalité par récurrence forte sur le nombre $n$ d'activités de l'instance.
Initialisation. Pour $n = 0$, la fonction renvoie la liste vide, seule famille possible : elle est de cardinal maximal.
Hérédité. Soit $n \geq 1$ ; supposons le résultat acquis pour toute instance d'au plus $n - 1$ activités. Soit $I$ une instance à $n$ activités et soit $a$ la première activité examinée, c'est-à-dire une activité de date de fin minimale ; la fonction la retient, puisque fin_courante vaut None.
Soit $S$ une famille compatible de cardinal maximal de $I$ : il en existe, le nombre de parties de $I$ étant fini. Elle est non vide, car la famille $\{a\}$ est compatible et de cardinal $1$. Notons $s$ l'activité de $S$ de date de fin minimale.
Premier temps, l'échange. Soit $t \in S$ avec $t \neq s$. Les activités $s$ et $t$ sont compatibles, donc $f(s) \leq d(t)$ ou $f(t) \leq d(s)$. Le second cas donnerait $f(t) \leq d(s) < f(s)$, ce qui contredit la minimalité de $f(s)$ dans $S$. Donc $f(s) \leq d(t)$. Comme $a$ est de date de fin minimale dans toute l'instance, $f(a) \leq f(s) \leq d(t)$ : l'activité $a$ est compatible avec $t$.
Posons $S' = (S \setminus \{s\}) \cup \{a\}$. D'après ce qui précède, $a$ est compatible avec chaque élément de $S \setminus \{s\}$, et ces éléments sont deux à deux compatibles comme éléments de $S$ : la famille $S'$ est donc compatible. De plus $a \notin S \setminus \{s\}$, sinon $a$ serait l'un des $t$ ci-dessus et vérifierait $d(a) \geq f(s) \geq f(a) > d(a)$, ce qui est impossible. Ainsi $|S'| = |S|$ : la famille $S'$ est de cardinal maximal et contient $a$.
Deuxième temps, le sous-problème. Notons $I'$ l'ensemble des activités $t$ de $I$ telles que $d(t) \geq f(a)$. Tout élément $t$ de $S' \setminus \{a\}$ est compatible avec $a$, donc vérifie $f(a) \leq d(t)$ ou $f(t) \leq d(a)$ ; le second cas donnerait $f(t) \leq d(a) < f(a) \leq f(t)$, ce qui est impossible. Donc $S' \setminus \{a\}$ est une famille compatible de $I'$.
Elle y est de cardinal maximal : si $T$ était une famille compatible de $I'$ de cardinal strictement supérieur à $|S'| - 1$, alors $T \cup \{a\}$ serait compatible, puisque tout $t \in T$ vérifie $d(t) \geq f(a)$, et de cardinal strictement supérieur à $|S'|$, ce qui contredirait la maximalité de $S'$.
Troisième temps, l'exécution. Toute activité $t$ de $I'$ vérifie $f(t) > d(t) \geq f(a)$, donc est examinée après $a$. Toute activité $t$ de $I \setminus I'$ examinée après $a$ vérifie $d(t) < f(a)$, et la variable fin_courante contient alors une date supérieure ou égale à $f(a)$ : une telle activité est donc rejetée. Après avoir retenu $a$, la fonction se comporte donc exactement comme si elle était lancée sur $I'$ : elle retient la première activité de $I'$ examinée, puis les suivantes selon le même test.
Comme $a \notin I'$, l'instance $I'$ compte au plus $n - 1$ activités : par hypothèse de récurrence, la fonction y retient $|S' \setminus \{a\}| = |S| - 1$ activités. Sur $I$, elle en retient donc $1 + (|S| - 1) = |S|$ : la famille renvoyée est de cardinal maximal.
Conclusion. Pour tout $n \in \mathbb{N}$, la fonction renvoie une famille compatible de cardinal maximal.
À retenir : l'échange remplace l'activité de $S$ qui finit le plus tôt par celle qui finit le plus tôt de toute l'instance, et c'est la minimalité de $f(a)$ qui garantit que la famille reste compatible ; la récurrence s'applique ensuite au sous-problème des activités qui commencent après $f(a)$.

Lignes fautives : sorted(activites, key=lambda a: a[1] - a[0]), la durée croissante, et sorted(activites), la date de début croissante. Les deux critères semblent raisonnables, et les deux sont faux.
Contre-exemple pour la durée : les activités $(0, 10)$, $(9, 11)$ et $(10, 20)$. Le critère de la durée retient d'abord $(9, 11)$, de durée $2$, qui est incompatible avec les deux autres : une seule activité. Le critère de la date de fin en retient deux, $(0, 10)$ et $(10, 20)$.
Contre-exemple pour la date de début : les activités $(0, 20)$, $(1, 2)$ et $(3, 4)$. Le critère de la date de début retient $(0, 20)$ et ne peut plus rien retenir : une seule activité, contre deux par la date de fin, $(1, 2)$ et $(3, 4)$.
Version correcte : sorted(activites, key=lambda activite: activite[1]). Le bon critère est celui qui libère la salle le plus tôt, et c'est le seul des trois pour lequel l'échange de la rédaction modèle fonctionne : l'activité de date de fin minimale se substitue à n'importe quelle autre sans gêner les suivantes, ce qu'une activité courte ou hâtive ne garantit pas.

Un système de pièces $c_1 > c_2 > \dots > c_k$ avec $c_k = 1$ est dit canonique lorsque, pour tout entier naturel $n$, le rendu glouton de $n$ utilise un nombre minimal de pièces. La condition $c_k = 1$ assure qu'un rendu existe pour tout montant. Le système de l'euro, $(200, 100, 50, 20, 10, 5, 2, 1)$ en centimes, est canonique ; le système $(4, 3, 1)$ ne l'est pas. Être canonique est une propriété du système de valeurs, pas de l'algorithme : le glouton ne change pas d'un système à l'autre, ce sont les valeurs qui décident.

Théorème : pour le système $(200, 100, 50, 20, 10, 5, 2, 1)$ des pièces en centimes et pour tout $n \in \mathbb{N}$, le rendu glouton de $n$ utilise un nombre minimal de pièces. La démonstration, exigible, repose sur des échanges élémentaires : dans un rendu de cardinal minimal, deux pièces de $1$ s'échangeraient contre une de $2$, trois pièces de $2$ contre $5 + 1$, deux pièces de $20$ et une de $10$ contre une de $50$. Chacun de ces échanges raccourcissant le rendu, un rendu minimal ne peut contenir la configuration échangée. On en tire que la somme des pièces strictement inférieures à une valeur $c$ y est toujours $< c$, ce qui force tout rendu minimal à contenir la plus grande pièce $\leq n$ : c'est exactement le choix glouton.

Démontrer que, pour le système $(200, 100, 50, 20, 10, 5, 2, 1)$ et pour tout entier naturel $n$, le rendu glouton de $n$ utilise un nombre minimal de pièces.
Soit $n \in \mathbb{N}$. Un rendu de $n$ est une famille de pièces du système, avec répétitions, de somme $n$. Il en existe, par exemple $n$ pièces de $1$, et tout rendu compte au plus $n$ pièces puisque chaque pièce vaut au moins $1$ : il existe donc un rendu de cardinal minimal. Fixons-en un, noté $M$, et pour chaque valeur $c$ du système, notons $a_c$ le nombre de pièces de valeur $c$ dans $M$.
Premier temps : les échanges. Chaque remplacement ci-dessous conserve la somme et diminue le nombre de pièces ; il contredirait donc la minimalité de $M$, et la configuration correspondante est impossible dans $M$.
Deux pièces de $1$ contre une pièce de $2$ : donc $a_1 \leq 1$.
Une pièce de $1$ et deux pièces de $2$ contre une pièce de $5$, soit trois pièces contre une : donc on n'a pas à la fois $a_1 \geq 1$ et $a_2 \geq 2$.
Trois pièces de $2$ contre une de $5$ et une de $1$, soit trois pièces contre deux : donc $a_2 \leq 2$.
Deux pièces de $5$ contre une de $10$ : donc $a_5 \leq 1$. Deux pièces de $10$ contre une de $20$ : donc $a_{10} \leq 1$.
Trois pièces de $20$ contre une de $50$ et une de $10$ : donc $a_{20} \leq 2$. Deux pièces de $20$ et une de $10$ contre une de $50$ : donc on n'a pas à la fois $a_{20} \geq 2$ et $a_{10} \geq 1$.
Deux pièces de $50$ contre une de $100$ : donc $a_{50} \leq 1$. Deux pièces de $100$ contre une de $200$ : donc $a_{100} \leq 1$.
Deuxième temps : la petite monnaie ne suffit jamais. Pour une valeur $c$ du système, notons $\sigma(c)$ la somme des pièces de $M$ de valeur strictement inférieure à $c$. Montrons que $\sigma(c) < c$ pour chaque valeur $c$.
$\sigma(1) = 0 < 1$ : aucune pièce du système n'a une valeur strictement inférieure à $1$, et la somme vide est nulle.
$\sigma(2) = a_1 \leq 1 < 2$.
$\sigma(5) = a_1 + 2a_2$ : si $a_1 = 1$, alors $a_2 \leq 1$ et $\sigma(5) \leq 3$ ; si $a_1 = 0$, alors $\sigma(5) = 2a_2 \leq 4$. Dans les deux cas $\sigma(5) \leq 4 < 5$.
$\sigma(10) = \sigma(5) + 5a_5 \leq 4 + 5 = 9 < 10$.
$\sigma(20) = \sigma(10) + 10a_{10} \leq 9 + 10 = 19 < 20$.
$\sigma(50) = \sigma(20) + 20a_{20}$ : si $a_{20} = 2$, alors $a_{10} = 0$, donc $\sigma(20) \leq 9$ et $\sigma(50) \leq 9 + 40 = 49$ ; sinon $a_{20} \leq 1$ et $\sigma(50) \leq 19 + 20 = 39$. Dans les deux cas $\sigma(50) \leq 49 < 50$.
$\sigma(100) = \sigma(50) + 50 a_{50} \leq 49 + 50 = 99 < 100$.
$\sigma(200) = \sigma(100) + 100 a_{100} \leq 99 + 100 = 199 < 200$.
Troisième temps : le choix glouton. Supposons $n \geq 1$ et notons $c$ la plus grande valeur du système inférieure ou égale à $n$ ; elle existe, car $1 \leq n$. Toute pièce de $M$ a une valeur inférieure ou égale à $n$, puisque la somme de $M$ vaut $n$ et que les valeurs sont strictement positives ; par maximalité de $c$, elle est donc inférieure ou égale à $c$. Si $M$ ne contenait aucune pièce de valeur $c$, toutes ses pièces seraient de valeur strictement inférieure à $c$ et l'on aurait $n = \sigma(c) < c \leq n$, ce qui est impossible. Donc $M$ contient au moins une pièce de valeur $c$, c'est-à-dire la pièce que le glouton rend en premier.
Quatrième temps : la récurrence. Montrons par récurrence forte sur $n$ que le rendu glouton de $n$ est de cardinal minimal.
Pour $n = 0$, le glouton ne rend aucune pièce, et c'est minimal.
Soit $n \geq 1$, le résultat étant supposé acquis pour tous les entiers de $0$ à $n - 1$. Avec les notations précédentes, $M$ contient une pièce de valeur $c$ ; la famille $M$ privée de cette pièce est un rendu de $n - c$, et elle y est de cardinal minimal, car un rendu de $n - c$ plus court donnerait, en lui ajoutant une pièce de valeur $c$, un rendu de $n$ plus court que $M$.
Le glouton, lui, rend d'abord une pièce de valeur $c$ puis traite le reste $n - c$ exactement comme il traiterait le montant $n - c$ proposé seul, puisqu'à chaque étape il sert la plus grande valeur inférieure ou égale au reste. Comme $0 \leq n - c < n$, l'hypothèse de récurrence donne que son rendu de $n - c$ compte $|M| - 1$ pièces. Le rendu glouton de $n$ compte donc $1 + (|M| - 1) = |M|$ pièces : il est de cardinal minimal.
Conclusion. Le système de l'euro est canonique.
À retenir : chaque borne sur $a_c$ vient d'un échange qui raccourcirait le rendu ; ces bornes donnent l'inégalité $\sigma(c) < c$, et c'est elle qui force tout rendu minimal à contenir la pièce choisie par le glouton.

Quand l'utiliser : l'énoncé demande « cet algorithme est-il optimal ? », « ce système est-il canonique ? », ou « montrer que ce critère ne convient pas ».
1) Se souvenir qu'une seule instance suffit : l'optimalité est un énoncé universel, sa négation est une existence.
2) Construire l'instance petite et entière : trois ou quatre candidats, des nombres à un chiffre. Les contre-exemples des gloutons se logent presque toujours dans les petits nombres.
3) Chercher l'instance là où le premier choix mange la place de deux meilleurs choix : une grosse pièce qui laisse un reste mal formé, un objet lourd qui empêche d'en prendre deux légers, une activité longue qui en bloque deux courtes.
4) Dérouler le glouton à la main, en écrivant ligne par ligne ce qu'il choisit, ce qui reste, et la valeur de sa solution.
5) Exhiber une solution réalisable strictement meilleure, vérifier qu'elle respecte toutes les contraintes de l'énoncé, et comparer les deux valeurs chiffrées.
6) Conclure sur l'énoncé exact : « le glouton n'est pas optimal pour ce système », et non « le glouton n'est jamais optimal ».
7) Vérifier enfin le contre-exemple au clavier (méthode suivante) : une erreur de calcul à la main peut faire croire qu'un théorème vrai est faux.

Montrer que le système de pièces $(4, 3, 1)$ n'est pas canonique.
Considérons le montant $n = 6$.
Déroulons le rendu glouton. La plus grande valeur inférieure ou égale à $6$ est $4$ : le glouton rend une pièce de $4$, et le reste vaut $2$. La plus grande valeur inférieure ou égale à $2$ est $1$ : le glouton rend deux pièces de $1$, et le reste vaut $0$. Le rendu glouton de $6$ est donc $4 + 1 + 1$, soit trois pièces.
Or $6 = 3 + 3$ est un rendu de $6$ avec deux pièces du système.
Comme $2 < 3$, le rendu glouton de $6$ n'est pas de cardinal minimal. Il existe donc un montant pour lequel le glouton n'est pas optimal : le système $(4, 3, 1)$ n'est pas canonique.
Vérification au clavier : rendu_glouton([4, 3, 1], 6) renvoie [4, 1, 1], tandis que la fonction rendu_minimal de la rédaction modèle « chercher le plus petit contre-exemple d'un système de pièces » renvoie 2.
À retenir : un contre-exemple se rédige en trois lignes chiffrées, le déroulé du glouton, une solution strictement meilleure, la comparaison ; et la conclusion porte sur ce système-là, sans généralisation abusive.

Quand l'utiliser : après avoir écrit un glouton et avant de croire qu'il est optimal ; et chaque fois qu'un énoncé demande le plus petit montant pour lequel un système de pièces met le glouton en défaut.
1) Écrire une fonction qui calcule l'optimum exact sur les petites instances, sans se soucier de son coût. Pour le rendu de monnaie, on remplit un tableau des minima de $0$ à $n$ : la case minimum[m] contient le nombre minimal de pièces pour le montant m, obtenu en essayant chaque valeur c du système et en ajoutant une pièce au minimum du montant m - c, déjà calculé.
2) Choisir une sentinelle pour « pas de rendu » : $n + 1$ convient, puisqu'un rendu d'un montant inférieur ou égal à $n$ compte au plus $n$ pièces. L'infini flottant float('inf') conviendrait aussi, les comparaisons restant exactes avec lui ; on préfère l'entier pour que la table ne contienne que des entiers, et parce que la sentinelle dit alors d'où elle vient. Le piège des flottants est ailleurs : il est dans les montants décimaux.
3) Balayer toute une famille d'instances, comparer les deux résultats, et renvoyer la première instance qui diffère.
4) Lire le résultat honnêtement : un montant renvoyé est un contre-exemple certain, à recopier sur la copie ; None ne démontre rien au-delà de la borne testée.
5) Ne jamais écrire « le balayage n'a rien trouvé, donc le glouton est optimal » : une propriété universelle se démontre par un argument d'échange.
Le coût du tableau des minima est $O(nk)$ pour un montant $n$ et $k$ valeurs, contre $O(k + N)$ pour le glouton : c'est le prix de la certitude, et c'est pourquoi on ne l'emploie que sur de petites instances.

Écrire une fonction qui calcule le nombre minimal de pièces d'un rendu, une fonction qui compte les pièces du rendu glouton, puis une fonction qui renvoie le plus petit montant, inférieur ou égal à une borne donnée, pour lequel le glouton n'est pas optimal. Les appliquer au système $(4, 3, 1)$ et au système de l'euro.

def rendu_minimal(pieces, n):
    """pieces : valeurs entieres strictement positives.
       n : entier naturel.
       Renvoie le nombre minimal de pieces totalisant n, ou None si aucun rendu n'existe."""
    impossible = n + 1
    minimum = [0] + [impossible] * n
    for montant in range(1, n + 1):
        for valeur in pieces:
            if valeur <= montant and minimum[montant - valeur] + 1 < minimum[montant]:
                minimum[montant] = minimum[montant - valeur] + 1
    return None if minimum[n] == impossible else minimum[n]


def nombre_glouton(pieces, n):
    """pieces : valeurs entieres strictement positives, rangees par ordre decroissant.
       n : entier naturel.
       Renvoie le nombre de pieces du rendu glouton de n, ou None si le glouton echoue."""
    reste = n
    rendues = 0
    for valeur in pieces:
        rendues += reste // valeur
        reste %= valeur
    return rendues if reste == 0 else None


def plus_petit_contre_exemple(pieces, borne):
    """pieces : valeurs entieres strictement positives, rangees par ordre decroissant.
       Renvoie le plus petit montant inferieur ou egal a borne pour lequel le glouton
       n'est pas optimal, ou None s'il n'y en a pas."""
    for n in range(1, borne + 1):
        optimal = rendu_minimal(pieces, n)
        if optimal is None:
            continue
        rendues = nombre_glouton(pieces, n)
        if rendues is None or rendues > optimal:
            return n
    return None

La fonction nombre_glouton refait le rendu glouton de la rédaction modèle « le rendu de monnaie glouton » en comptant les pièces au lieu de les écrire : la comparaison ne demande que leur nombre, et le bloc se suffit ainsi à lui-même, sans appeler une fonction définie sur une autre carte.
Justification du tableau. Notons $m(x)$ le nombre minimal de pièces totalisant $x$, avec $m(x) = +\infty$ s'il n'existe aucun rendu. On a $m(0) = 0$, et pour $x \geq 1$, tout rendu de $x$ contient au moins une pièce, de valeur $c_i \leq x$ ; en la retirant, on obtient un rendu de $x - c_i$, d'où $m(x) = 1 + \min \{\, m(x - c_i) \ :\ c_i \leq x \,\}$. La boucle remplit les cases par montants croissants, donc la case $x - c_i$ est calculée avant la case $x$ : l'invariant « après le tour $x$, les cases $0$ à $x$ contiennent le minimum, ou la sentinelle » est conservé. La sentinelle $n + 1$ est inatteignable par un vrai rendu, puisque chaque pièce vaut au moins $1$.
Exécution.

print(plus_petit_contre_exemple([4, 3, 1], 100))
print(plus_petit_contre_exemple([200, 100, 50, 20, 10, 5, 2, 1], 1000))

affiche

6
None

Lecture du résultat. Le montant $6$ est un contre-exemple certain pour le système $(4, 3, 1)$ : le glouton y rend trois pièces au lieu de deux. Pour le système de l'euro, le balayage ne trouve rien jusqu'à $1000$ centimes, ce qui ne démontre pas que ce système est canonique : cela se démontre par les échanges de la rédaction modèle correspondante.
Coût. La fonction rendu_minimal coûte $O(nk)$ et le balayage l'appelle pour chaque montant, d'où $O(b^2 k)$ pour une borne $b$ ; les $O(k)$ de chaque comptage glouton n'y changent rien. C'est un outil de vérification, pas un algorithme de production.
À retenir : on confronte un glouton à l'optimum exact sur de petites instances ; le balayage fournit des contre-exemples, jamais une preuve.

On dispose de $n$ objets, l'objet $i$ ayant un poids $p_i > 0$ et une valeur $v_i > 0$, et d'un sac de capacité $W > 0$. Dans la version fractionnaire, on peut n'emporter qu'une part de chaque objet : une solution réalisable est un vecteur $(x_1, \dots, x_n) \in [0,1]^n$ tel que $\sum_{i=1}^{n} x_i p_i \leq W$, et l'on maximise $\sum_{i=1}^{n} x_i v_i$. La valeur massique de l'objet $i$ est le quotient $v_i / p_i$. Le critère glouton est la valeur massique décroissante : on sert les objets les plus rentables au kilogramme, entièrement tant qu'ils tiennent, puis l'on complète le sac avec une part du suivant.

Théorème : pour le sac à dos fractionnaire, l'algorithme qui prend les objets par valeur massique décroissante, entiers tant qu'ils tiennent puis la part qui complète exactement la capacité, renvoie une solution optimale. Les hypothèses comptent toutes : les poids sont strictement positifs (sinon la valeur massique n'existe pas), les valeurs sont strictement positives (une valeur nulle ne ferait rien gagner, et la rédaction modèle se sert de cette inégalité stricte au moment décisif de sa preuve), et les parts sont fractionnaires, c'est-à-dire $x_i \in [0,1]$. Si l'on impose $x_i \in \{0, 1\}$, c'est le sac à dos entier, et la conclusion tombe : voir le piège correspondant. Le coût est celui du tri, soit $O(n \log n)$.

Les objets sont des couples d'entiers (poids, valeur) strictement positifs et la capacité un entier lui aussi strictement positif. Écrire une fonction gloutonne qui renvoie les parts prises et la valeur totale, exacte, puis démontrer son optimalité.

from fractions import Fraction

def sac_fractionnaire(objets, capacite):
    """objets : liste de couples (poids, valeur) d'entiers strictement positifs.
       capacite : entier strictement positif.
       Renvoie la liste des couples (objet, part prise) et la valeur totale, exacte."""
    restante = Fraction(capacite)
    prises = []
    valeur_totale = Fraction(0)
    for poids, valeur in sorted(objets, key=lambda objet: Fraction(objet[1], objet[0]), reverse=True):
        if restante == 0:
            break
        part = min(Fraction(1), restante / poids)
        prises.append(((poids, valeur), part))
        valeur_totale += part * valeur
        restante -= part * poids
    return prises, valeur_totale

Les parts sont des Fraction et non des flottants : les comparaisons et l'égalité restante == 0 sont alors exactes.
Sur les objets [(6, 12), (5, 9), (5, 9)] et la capacité 10, la fonction prend l'objet $(6, 12)$ en entier puis la part $\frac{4}{5}$ d'un objet $(5, 9)$, pour une valeur totale $12 + \frac{4}{5} \times 9 = \frac{96}{5}$, c'est-à-dire $19{,}2$.
Démontrons l'optimalité. Numérotons les objets dans l'ordre de traitement, de sorte que $\frac{v_1}{p_1} \geq \frac{v_2}{p_2} \geq \dots \geq \frac{v_n}{p_n}$, et notons $x = (x_1, \dots, x_n)$ la solution renvoyée et $v(y) = \sum_{i=1}^n y_i v_i$ la valeur d'une solution $y$.
Premier cas : $\sum_{i=1}^n p_i \leq W$. La fonction prend alors tous les objets entiers, donc $x_i = 1$ pour tout $i$. Pour toute solution réalisable $y$, on a $y_i \leq 1$ et $v_i > 0$, donc $v(y) \leq \sum_{i=1}^n v_i = v(x)$ : la solution $x$ est optimale.
Second cas : $\sum_{i=1}^n p_i > W$. La fonction s'arrête alors sur le premier objet qui déborde et n'en prend que la part qui complète la capacité, donc $\sum_{i=1}^n x_i p_i = W$.
Soit $y$ une solution optimale ; il en existe une, car l'ensemble des solutions réalisables est une partie fermée bornée de $\mathbb{R}^n$ et la fonction $v$ y est continue. Montrons d'abord que $\sum_{i=1}^n y_i p_i = W$. Sinon, $\sum_{i=1}^n y_i p_i < W$, et il existe un indice $j$ tel que $y_j < 1$, car si toutes les parts valaient $1$ on aurait $\sum_{i=1}^n y_i p_i = \sum_{i=1}^n p_i > W$. En augmentant $y_j$ d'une quantité strictement positive et assez petite pour que la capacité soit respectée et que $y_j$ reste inférieur à $1$, on obtient une solution réalisable de valeur strictement supérieure, car $v_j > 0$, ce qui contredit l'optimalité de $y$.
Supposons $y \neq x$ et notons $i$ le plus petit indice tel que $y_i \neq x_i$.
Par construction, $x_i$ est la plus grande part de l'objet $i$ que l'on puisse prendre après avoir pris $x_1, \dots, x_{i-1}$, c'est-à-dire $x_i = \min\left(1, \frac{W - \sum_{k < i} x_k p_k}{p_i}\right)$. Comme $y$ est réalisable et que $y_k = x_k$ pour $k < i$, on a $y_i \leq 1$ et $y_i p_i \leq W - \sum_{k<i} x_k p_k$, donc $y_i \leq x_i$, et finalement $y_i < x_i$.
Posons $\delta = (x_i - y_i) p_i > 0$. Des égalités $\sum_{k} y_k p_k = W = \sum_k x_k p_k$ et $y_k = x_k$ pour $k < i$, on tire
$\sum_{k > i} y_k p_k = \sum_{k \geq i} x_k p_k - y_i p_i \geq x_i p_i - y_i p_i = \delta$.
La solution $y$ place donc une masse au moins égale à $\delta$ sur les indices strictement supérieurs à $i$. Retirons-en exactement $\delta$, réparti comme on veut sur ces indices, et ajoutons-la à l'objet $i$ : on obtient $y'$ défini par $y'_k = y_k$ pour $k < i$, $y'_i = x_i$, et $y'_k \leq y_k$ pour $k > i$ avec $\sum_{k>i} (y_k - y'_k) p_k = \delta$. Toutes les parts restent dans $[0,1]$ et la masse totale est inchangée, égale à $W$ : la solution $y'$ est réalisable.
Comparons les valeurs. En notant $\mu_k = (y_k - y'_k) p_k$ la masse retirée à l'objet $k$, on a
$v(y') - v(y) = \delta \frac{v_i}{p_i} - \sum_{k > i} \mu_k \frac{v_k}{p_k}$.
Or $\frac{v_k}{p_k} \leq \frac{v_i}{p_i}$ pour $k > i$ et $\mu_k \geq 0$, donc $\sum_{k>i} \mu_k \frac{v_k}{p_k} \leq \frac{v_i}{p_i} \sum_{k>i} \mu_k = \delta \frac{v_i}{p_i}$, et $v(y') - v(y) \geq 0$.
Ainsi $y'$ est encore optimale et coïncide avec $x$ sur les indices $1, \dots, i$ : l'échange a augmenté d'au moins une unité la longueur du préfixe commun. En le répétant au plus $n$ fois, on obtient une solution optimale égale à $x$ : la solution gloutonne est donc optimale.
À retenir : l'échange transfère une masse $\delta$ des objets de faible valeur massique vers celui que le glouton aurait pris davantage ; c'est l'ordre des valeurs massiques, et lui seul, qui garantit que la valeur ne baisse pas.

Phrase fautive : « on ne peut pas couper les objets, mais le glouton par valeur massique décroissante donne quand même l'optimum ».
Contre-exemple chiffré : capacité $10$, objets $(6, 12)$, $(5, 9)$ et $(5, 9)$, donnés par (poids, valeur). Les valeurs massiques valent $2$, $1{,}8$ et $1{,}8$. Le glouton prend donc l'objet de poids $6$, de valeur $12$ ; il reste $4$ unités de capacité, dans lesquelles aucun des deux objets de poids $5$ ne tient : il obtient $12$. Or les deux objets de poids $5$ tiennent ensemble dans le sac et donnent $18$. Le glouton n'est donc pas optimal pour le sac à dos entier.
Version correcte : pour le sac à dos entier, le glouton est une heuristique, ici à $\frac{12}{18} = \frac{2}{3}$ de l'optimum, et il n'existe pas d'algorithme glouton qui le résolve en général. L'optimum exact se calcule par un tableau des sous-problèmes, comme le nombre minimal de pièces d'un rendu. La version fractionnaire, elle, reste optimale, et sa valeur majore l'optimum entier : ici $19{,}2 \geq 18$, ce qui en fait une borne utile.

Les données sont les mêmes que pour la sélection d'activités, mais on veut cette fois toutes les réaliser : il s'agit de répartir $n$ activités entre des salles, de sorte que deux activités affectées à une même salle soient compatibles, en utilisant un nombre minimal de salles. C'est donc un problème de minimisation. Le critère glouton est la date de début croissante : on examine les activités dans l'ordre où elles commencent, on réutilise la salle qui se libère le plus tôt lorsqu'elle est déjà libre, et l'on ouvre une salle neuve sinon. Le suivi de la salle qui se libère le plus tôt se fait avec un tas, celui du module heapq (voir le thème Graphes : représentation et parcours).

Quand l'utiliser : le problème est une minimisation (un nombre de salles, de machines, de tournées) et l'échange est malcommode parce qu'il n'y a pas de « premier choix » évident à faire entrer dans une solution optimale.
1) Repérer dans l'instance une obstruction : un paquet de candidats que toute solution réalisable est obligée de séparer, par exemple des activités qui contiennent toutes un même instant.
2) Écrire la borne inférieure sous la forme « toute solution réalisable utilise au moins $m$ ressources », en la justifiant à partir des contraintes du problème seules : l'algorithme ne doit pas apparaître dans cette étape.
3) Écrire la borne supérieure : « l'algorithme utilise exactement $m$ ressources ». On la lit en général au moment où il ouvre la dernière ressource, en décrivant l'état de toutes les autres à cet instant.
4) Conclure par encadrement : l'optimum est compris entre $m$ et $m$, donc il vaut $m$, et l'algorithme est optimal.
5) Vérifier séparément que l'algorithme produit une solution réalisable : une borne atteinte par une répartition fausse ne démontre rien.

Écrire une fonction qui répartit des activités (debut, fin) entre des salles, deux activités d'une même salle devant être compatibles, puis démontrer que le nombre de salles utilisées est minimal.

import heapq

def allocation_salles(activites):
    """activites : liste de couples (debut, fin) d'entiers avec debut < fin.
       Renvoie la liste des salles, chaque salle etant la liste des activites qui lui
       sont affectees. Le nombre de salles est minimal."""
    salles = []
    liberations = []  # tas des couples (fin de la derniere activite, numero de salle)
    for debut, fin in sorted(activites):
        if liberations and liberations[0][0] <= debut:
            _, numero = heapq.heappop(liberations)
            salles[numero].append((debut, fin))
        else:
            numero = len(salles)
            salles.append([(debut, fin)])
        heapq.heappush(liberations, (fin, numero))
    return salles

Sur l'exemple [(0, 4), (1, 3), (2, 6), (5, 7), (6, 9), (8, 10)], la fonction renvoie trois salles : [(0, 4), (6, 9)], [(1, 3), (5, 7)] et [(2, 6), (8, 10)].
La répartition est valide. Dans une salle donnée, les activités sont ajoutées par dates de début croissantes, et chaque nouvelle activité $a$ n'y est ajoutée que si la date de fin de la dernière activité $b$ de cette salle vérifie $f(b) \leq d(a)$. Comme $f(a) > d(a) \geq f(b)$, les dates de fin d'une même salle sont croissantes : la dernière est donc la plus grande, et $a$ est compatible avec toutes les activités déjà présentes dans la salle, pas seulement avec la dernière.
Invariant du tas : chaque tour retire au plus un couple et en ajoute exactement un, donc le tas contient à tout instant un couple par salle ouverte, celui de la dernière activité qui lui a été affectée.
Notons $k$ le nombre de salles renvoyées ; toutes les activités sont affectées, puisque chaque tour de boucle en affecte une.
Borne inférieure. Si $k = 0$, la liste d'activités est vide et il n'y a rien à démontrer ; si $k = 1$, toute répartition d'au moins une activité utilise au moins une salle. Supposons $k \geq 2$ et considérons le tour où la $k$-ième salle est ouverte, pour une activité $a = (d, f)$. Le tas n'est pas vide à ce moment, donc la condition liberations[0][0] <= debut est fausse : le minimum du tas est strictement supérieur à $d$, donc les dates de fin des dernières activités des $k - 1$ salles déjà ouvertes sont toutes strictement supérieures à $d$. Notons $b_1, \dots, b_{k-1}$ ces dernières activités. Chacune a été examinée avant $a$, donc $d(b_j) \leq d$ puisque les activités sont triées par date de début, et $f(b_j) > d$ : l'intervalle $[d(b_j), f(b_j)[$ contient l'instant $d$. L'intervalle de $a$ le contient aussi, car $d < f$.
Les $k$ activités $b_1, \dots, b_{k-1}, a$ contiennent donc toutes l'instant $d$ : elles sont deux à deux incompatibles, et toute répartition valide les place dans $k$ salles deux à deux distinctes. Toute solution réalisable utilise donc au moins $k$ salles.
Borne supérieure et conclusion. La fonction en utilise exactement $k$, et l'on vient de voir que l'optimum est supérieur ou égal à $k$ : l'optimum vaut $k$, et le nombre de salles utilisées est minimal.
Coût. Le tri coûte $O(n \log n)$ ; chaque activité provoque au plus une extraction et une insertion dans le tas, en $O(\log n)$ chacune. Le coût total est $O(n \log n)$.
Vérification. Le nombre maximal d'activités contenant un même instant vaut $3$ sur cet exemple, ce que confirme un comptage direct.

def simultanees_maximum(activites):
    """Nombre maximal d'activites qui contiennent un meme instant."""
    return max(sum(1 for d, f in activites if d <= t < f) for t, _ in activites)


print(simultanees_maximum([(0, 4), (1, 3), (2, 6), (5, 7), (6, 9), (8, 10)]))

affiche

3

À retenir : pour une minimisation, on encadre ; la borne inférieure vient d'un paquet de candidats deux à deux incompatibles, que l'on lit au moment précis où l'algorithme ouvre sa dernière ressource.