Sélection d'Activités
Algorithmique classique
Enonce
Étant donné des activités avec leurs heures de debut et fin, sélectionner le maximum d'activités compatibles (non chevauchantes). Approche gloutonne.
Signature attendue
def selection_activites(debut: list, fin: list) -> list:Exemples
selection_activites([1, 3, 0, 5, 8, 5], [2, 4, 6, 7, 9, 9])→[0, 1, 3, 4]len(selection_activites([1, 3, 0, 5, 8, 5], [2, 4, 6, 7, 9, 9]))→4
📖 Rappel de cours
On trie par date de fin croissante et on prend chaque activité compatible avec la précédente retenue. Ce glouton-là est optimal, et se démontre.
⚠ Le piège : Trier par durée ou par date de début donne un résultat sous-optimal. C'est la date de fin qui laisse le plus de place aux suivantes.
← Exercices Python pour la prépa — CPGE scientifique et ECG
Exercices du meme theme
- Degré des Sommets
- Composantes Connexes
- Rendu de Monnaie Glouton
- Sac à Dos Fractionnaire
- Couverture d'Intervalles
- Codage de Huffman Simplifié
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.