Un glouton prouvé optimal existe

def activites(intervalles):
    """Nombre maximal d'activites compatibles : glouton par fin CROISSANTE.

    Ce glouton-la est PROUVE optimal.
    """
    tries = sorted(intervalles, key=lambda x: x[1])
    fin, choisies = float("-inf"), []
    for debut, f in tries:
        if debut >= fin:
            choisies.append((debut, f))
            fin = f
    return choisies

def activites_exhaustif(intervalles):
    """Oracle : toutes les parties, pour de petites instances."""
    meilleur = 0
    for r in range(len(intervalles) + 1):
        for combi in itertools.combinations(sorted(intervalles), r):
            if all(combi[i][1] <= combi[i + 1][0] for i in range(len(combi) - 1)):
                meilleur = max(meilleur, r)
    return meilleur


I = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11)]
assert len(activites(I)) == 3
assert activites_exhaustif(I) == 3

for _ in range(300):                    # 300 instances aleatoires
    inter = []
    for _ in range(random.randint(1, 7)):
        a = random.randint(0, 10)
        inter.append((a, random.randint(a + 1, a + 6)))
    assert len(activites(inter)) == activites_exhaustif(inter)

L'idée de la preuve, en deux phrases. Choisir l'activité qui finit le plus tôt laisse le plus de temps possible pour toutes les suivantes ; on montre alors que toute solution optimale peut être transformée, sans perdre d'activité, en une solution qui commence par ce choix. Un tel argument d'« échange » est la façon standard de prouver qu'un glouton est optimal — et c'est justement ce qu'on ne peut pas faire pour le rendu de monnaie avec $[6,4,1]$.

Le même glouton, avec un autre critère, échoue.

def activites_duree(intervalles):
    """Variante : la plus COURTE d'abord."""
    tries = sorted(intervalles, key=lambda x: x[1] - x[0])
    pris = []
    for d, f in tries:
        if all(f <= a or d >= b for a, b in pris):
            pris.append((d, f))
    return pris

piege = [(0, 5), (4, 6), (5, 10)]
assert len(activites_duree(piege)) == 1     # elle prend (4,6), qui bloque les deux autres
assert len(activites(piege)) == 2           # (0,5) puis (5,10)

La plus courte activité, $(4,6)$, chevauche les deux autres et les élimine à elle seule. **Ce n'est pas « le glouton » qui est optimal ou non : c'est le critère.** Deux stratégies gloutonnes sur le même problème, l'une prouvée optimale, l'autre fausse sur trois intervalles.