Activity Selection

Le problème : maximiser les activités sans conflit

Vous avez plein d'activités avec des heures de début et de fin. Comment en choisir le maximum sans qu'elles se chevauchent ?

C'est un problème classique en informatique, connu sous le nom de Activity Selection Problem. On le retrouve partout : planification de salles de réunion, allocation de processeurs, gestion d'agendas...

L'intuition naïve serait de choisir les tâches les plus courtes, ou celles qui commencent le plus tôt. Mais ces approches ne fonctionnent pas toujours.

L'astuce contre-intuitive : trier par heure de FIN

La clé de l'algorithme est simple mais surprenante : on ne regarde pas quand une tâche commence, mais quand elle FINIT.

En triant toutes les activités par heure de fin croissante, on libère le créneau le plus tôt possible pour caser la prochaine tâche.

L'algorithme glouton, étape par étape

Prenons un exemple concret avec 5 activités :

• A1 [1-4], A2 [3-5], A3 [0-6], A4 [5-7], A5 [8-9]

Étape 1 : Trier par heure de fin

On trie TOUT par heure de FIN croissante :

Étape 2 : Sélectionner la première

On prend toujours la PREMIÈRE de la liste triée. C'est notre base : A1 [1-4]. Dernière fin = 4.

Étape 3 : Vérifier les suivantes

• A2 commence à 3... c'est avant la fin de A1 (4). CONFLIT ! On la passe.
• A3 commence à 0... c'est aussi avant 4. CONFLIT ! On la passe.
• A4 commence à 5... c'est après la fin de A1 (4). On la prend ! Nouvelle dernière fin = 7.
• A5 commence à 8... c'est après 7. On la prend !

Résultat

3 activités compatibles : A1, A4, A5. C'est le maximum possible !

Pourquoi ça marche ?

L'algorithme glouton fonctionne ici parce qu'en choisissant toujours l'activité qui finit le plus tôt, on maximise le temps restant pour les activités suivantes. C'est un choix localement optimal qui s'avère être globalement optimal.

La preuve mathématique repose sur le fait qu'il existe toujours une solution optimale qui inclut l'activité finissant le plus tôt. On peut donc la choisir sans risque, puis résoudre le sous-problème restant.

L'implémentation

Toute la "magie" repose sur le tri initial par heure de fin. C'est une solution très efficace en O(N log N) (dominée par le tri), souvent utilisée pour planifier des ressources partagées.

interface ActivityInterface {
  id: string;
  start: number;
  finish: number;
}
 
// Données de l'exemple de la BD
const activities: ActivityInterface[] = [
  { id: 'A1', start: 1, finish: 4 },
  { id: 'A2', start: 3, finish: 5 },
  { id: 'A3', start: 0, finish: 6 },
  { id: 'A4', start: 5, finish: 7 },
  { id: 'A5', start: 8, finish: 9 },
];
 
function solveActivitySelection(list: ActivityInterface[]): ActivityInterface[]
{
  // 1. LE POINT CLÉ : Trier par heure de FIN croissante
  // On utilise une copie [...] pour ne pas muter le tableau original
  const sorted = [...list].sort((a, b) => a.finish - b.finish);
 
  const selected: ActivityInterface[] = [];
 
  // 2. Base : On sélectionne toujours la première activité après le tri
  if (sorted.length > 0) {
    selected.push(sorted[0]);
  }
 
  // 3. Glouton : On cherche la prochaine compatible
  let lastFinishTime = sorted[0].finish;
 
  for (let i = 1; i < sorted.length; i++) {
    // Si l'activité commence après (ou en même temps) que la fin de la précédente
    if (sorted[i].start >= lastFinishTime) {
      selected.push(sorted[i]);
      // Mise à jour de la dernière heure de fin
      lastFinishTime = sorted[i].finish;
    }
  }
 
  return selected;
}
 
const result = solveActivitySelection(activities);
 
// Affichage du résultat (ids uniquement pour la lisibilité)
console.log("Activités retenues :", result.map(a => a.id));
 
// ------ Logs de sortie ------
// Activités retenues : [ 'A1', 'A4', 'A5' ]

Quand l'utiliser ?

L'Activity Selection est un cas d'école des algorithmes gloutons. On retrouve ce pattern dans :

• La planification de salles : maximiser le nombre de réunions dans une salle
• L'allocation de ressources : processeurs, machines, véhicules
• Les emplois du temps : caser un maximum de cours sans chevauchement
• Les intervalles en général : tout problème de type "interval scheduling"

Attention aux variantes

Cet algorithme maximise le nombre d'activités. Si l'objectif est de maximiser le temps total occupé ou de prioriser certaines tâches par importance, il faut passer à la programmation dynamique (Weighted Job Scheduling).