human
Étant donné N tâches où chaque tâche est représentée par les trois éléments suivants : (1) heure de début, (2) heure de fin, (3) profit ou valeur associée (>= 0). Écrivez du code Python qui trouve le sous-ensemble de tâches avec le profit maximum tel que deux tâches ne se chevauchent pas
gpt
Il s'agit d'un problème classique en informatique appelé planification pondérée des tâches, qui a une solution efficace utilisant la programmation dynamique. Voici une implémentation Python de cette solution :

```
# Importation du module suivant pour trier le tableau en fonction de notre fonction de comparaison personnalisée
from functools import cmp_to_key


# Une tâche a une heure de début, une heure de fin et un profit
class Tâche:

    def __init__(self, début, fin, profit):
        self.début = début
        self.fin = fin
        self.profit = profit


# Une fonction utilitaire utilisée pour trier les événements selon l'heure de fin
def comparaison_tâche(t1, t2):
    return t1.fin < t2.fin


# Trouve la dernière tâche (dans le tableau trié) qui ne se chevauche pas avec la tâche[i]. Si aucune tâche compatible n'existe, renvoie -1.
def dernière_sans_conflit(arr, i):
    for j in range(i - 1, -1, -1):
        if arr[j].fin <= arr[i - 1].début:
            return j
    return -1


# La fonction principale qui renvoie le profit maximum possible à partir du tableau donné de tâches
def dernier_sans_conflit(arr, n):

    # Trie les tâches selon l'heure de fin
    arr = sorted(arr, key=cmp_to_key(comparaison_tâche))

    # Crée un tableau pour stocker les solutions des sous-problèmes.
    # dp[i] stocke le profit pour les tâches jusqu'à arr[i] (y compris arr[i])
    dp = [None for _ in range(n)]
    dp[0] = arr[0].profit

    # Remplit les entrées du tableau de manière récursive
    for i in range(1, n):
        # Trouve le profit en incluant la tâche actuelle
        profit = arr[i].profit
        lsc = dernière_sans_conflit(arr, i)

        if lsc != -1:
            profit += dp[lsc]

        # Stocke le maximum entre l'inclusion et l'exclusion de la tâche
        dp[i] = max(profit, dp[i - 1])

    # Renvoie le profit maximum lors de la dernière étape
    return dp[-1]
```

Bien que cette implémentation ait une complexité temporelle de O(n^2) pour des raisons de simplicité, la solution peut être optimisée à O(n*logn) en remplaçant la recherche linéaire dans dernière_sans_conflit() par une recherche binaire.