Problème Vous avez n activités avec leurs heures de début et de fin. Sélectionnez le nombre maximal d'activités pouvant être effectuées par une seule personne, en supposant qu'une personne ne peut travailler que sur une seule activité à la fois.
Exemple n°1
Considérer les 3 activités suivantes triées par heure de finition :
debut[] = {10, 12, 20};
fin[] = {20, 25, 30};Une personne peut effectuer au plus deux activités : activité 1 et 3
Exemple n°2
Considérer les 6 activités suivantes triées par heure de finition :
debut[] = {1, 3, 0, 5, 8, 5};
fin[] = {2, 4, 6, 7, 9, 9};Une personne peut effectuer au plus quatre activités : (1, 2, 4 et 5)
Choix glouton
Le choix glouton consiste à toujours choisir l'activité suivante dont l'heure de fin est la plus petite des activités restantes et l'heure de début supérieure ou égale à l'heure de fin de l'activité précédemment sélectionnée. Nous pouvons trier les activités en fonction de leur heure de fin, de sorte que nous considérions toujours la prochaine activité comme une activité de temps de finition minimum.
1. Trier les activités en fonction de l'heure de fin
2. Sélectionner et afficher la première activité du tableau trié
3. Pour chaque activité restante dans le tableau trié :
Si l'heure de début de cette activité est supérieure ou égale
à l'heure de fin de l'activité précédemment sélectionnée :
Sélectionner et afficher cette activitédef MaxActivite(debut, fin):
n = len(fin)
print("voici les activités sélectionnées")
# choisir la première activité
i = 0
print(i+1)
for j in range(1, n):
if debut[j] >= fin[i]:
print(j+1)
i = j
# Tester la fonction
debut = [1, 3, 0, 5, 8, 5]
fin = [2, 4, 6, 7, 9, 9]
MaxActivite(debut, fin) Sortie
voici les activités sélectionnées 1 2 4 5
Sortie
// La sortie apparaîtra ici…
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.