Problème des gymnases

On souhaite rédiger un algorithme glouton pour résoudre le problème des gymnases.

On utiliseras donc une liste de tuples où chaque tuple est composé d'une string avec le nom de l'activité, un entier pour l'heure de début, un entier pour l'heure de fin.

Dans l'exemple ci-dessous, on obtient :

1
activites = [
2
    ("Basket-ball", 540, 630),
3
    ("Badminton", 570, 645),
4
    ("Tennis de table", 615, 675),
5
    ("Volley-ball", 630, 720),
6
    ("Gymnastique", 660, 705)]
Tableau des demandes de réservations

Sport

Début

Fin

Basket-ball

9h00

10h30

Badminton

9h30

10h45

Tennis de table

10h15

11h15

Volley-ball

10h30

12h00

Gymnastique

11h00

11h45

Question

À l'aide du tableau des activités données en introduction, rédiger le contenu de la variable activites.

Solution

1
activites = [
2
    ("Basket-ball",     540, 630),
3
    ("Badminton",       570, 645),
4
    ("Tennis de table", 615, 675),
5
    ("Volley-ball",     630, 720),
6
    ("Gymnastique",     660, 705),
7
    ("Handball",        690, 765),
8
    ("Escalade",        735, 795),
9
    ("Danse",           750, 810),
10
    ("Boxe française",  795, 855),
11
    ("Futsal",          826, 885)
12
]

Question

Comme spécifié dans le cours, on doit d'abord trier la liste des activités par date de fin.

Modifier la fonction tri suivante pour trier selon la date de fin. La fonction actuelle trie selon la date de début.

1
def tri(activite):
2
    activite.sort(key=lambda tup: tup[1])

Indice

La méthode sort, appliqué à une liste, trie la liste selon la clef passée en argument.

Indice

Le mot clef lambda, permet de créer une fonction temporaire sans nom.

Solution

1
def tri(activite):
2
    activite.sort(key=lambda tup: tup[2])

Prochaine activité

On cherche désormais à connaître la prochaine activité à choisir, connaissant le prochain créneau disponible.

Pour chaque activité non encore choisie, on retire les activités qu'on ne peut choisir, car elles chevauchent les activités en cours.

On choisit alors l'activité qui est la prochaine à finir.

Question

Compléter la fonction prochaine_activite qui renvoie la prochaine activité disponible qui termine le plus tôt.

1
def prochaine_activite(activite, dispo):
2
    while len(activite) > 0:
3
        if activite[0][1] < dispo:
4
            ...
5
        else:
6
            ...

Question

Maintenant que nous avons la fonction prochaine_activite, écrire une fonction glouton, telle que :

Entrées :

  • activites : une liste d'activités telle que définie précédemment

Sorties :

  • une liste d'activités optimale et qui ne se chevauche pas

Question

Pour aller plus loin :

Définir la fonction glouton_k, telle que :

Entrées :

  • activites : une liste d'activités telle que définie précédemment

  • k : un entier représentant le nombre de gymnase disponible

Sorties :

  • une liste de liste d'activités optimale pour chaque gymnase.