Introduction aux algorithmes gloutons

def glouton(donnees):
    solution = []
    while not solution_complete(solution):
        choix = meilleur_choix(donnees, solution)
        if choix_valide(choix, solution):
            solution.append(choix)
    return solution

def algorithme_glouton(donnees):
    # ÉTAPE 1 : TRI selon le critère glouton — O(n log n)
    donnees_triees = sorted(donnees, key=critere_glouton)

    # ÉTAPE 2 : TRAITEMENT LINÉAIRE — O(n)
    solution = []
    for element in donnees_triees:
        if condition_faisabilite(solution, element):
            solution.append(element)

    return solution

def ordonnancement_glouton(taches):
    """
    Ordonnancement optimal par la règle de Smith.
    taches : liste de tuples (nom, durée, poids)
    Trie par d_i / p_i croissant → minimise la somme pondérée des Cᵢ.
    """
    taches_triees = sorted(taches, key=lambda T: T[1] / T[2])
    temps, somme = 0, 0

    for nom, d, p in taches_triees:
        temps += d
        somme += p * temps

    return taches_triees, somme


# Exemple
taches = [("A", 3, 2), ("B", 2, 4), ("C", 4, 1)]
ordre, cout = ordonnancement_glouton(taches)
print(f"Ordre : {ordre}")
print(f"Coût total associé = {cout}")

def selection_activites(activites):
    """
    Sélectionne le maximum d'activités compatibles.
    activites : liste de tuples (nom, debut, fin)
    Trie par heure de fin croissante → choisit celle qui se termine le plus tôt.
    """
    activites_triees = sorted(activites, key=lambda x: x[2])
    selection      = []
    fin_precedente = 0

    for nom, debut, fin in activites_triees:
        if debut >= fin_precedente:       # activité compatible
            selection.append((nom, debut, fin))
            fin_precedente = fin          # mettre à jour la dernière fin

    return selection


# Exemple
A = [("A1",1,4),  ("A2",3,5),  ("A3",0,6),  ("A4",5,7),
     ("A5",3,9),  ("A6",5,9),  ("A7",6,10), ("A8",8,11),
     ("A9",8,12), ("A10",2,14)]

res = selection_activites(A)
print("Activités sélectionnées :", res)