Problème de la sélection d'activités
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 :
considérer les 3 activités suivantes triées par 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
considérer les 6 activités suivantes triées par 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)
debut[] = {10, 12, 20};
fin[] = {20, 25, 30};
Une personne peut effectuer au plus deux activités. activité 1 et 3
considérer les 6 activités suivantes triées par 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)
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.
- Trier les activités en fonction de l'heure de fin
- Sélectionner et afficher la première activité du tableau trié
- Faire pour les activités restantes 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ées selectionné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)
voici les activitées selectionnées
1
2
4
5
Partager ce cours avec tes amis :
Rédigé par
ESSADDOUKI
Mostafa
