Il nous est demandé de créer un algorithme qui détermine le nombre minimum de salles de cours nécessaire au déroulement d'une journée d'école. La difficulté réside dans le fait que les cours peuvent se chevaucher, mais deux cours ne peuvent partager une salle.

Les données sont fournies sous forme d'un fichier JSON contenant une liste de sessions. Chaque session est définie par une heure de début (format HH:MM), une heure de fin (format HH:MM), le nom du cours et le nom de l'intervenant. Un cours se terminant à 14:00 peut être suivi d'un autre commençant à 14:00 dans la même salle.

J'ai commencé par me représenter sur une feuille de papier plusieurs cas de figure à 2, 3 et 4 salles.

Cela m'a permis de mettre à jour que seuls les points "start" et "end" de chaque cours m'étaient utiles. En les triant du plus tôt au plus tard et en les associant à un compteur, je peux déterminer à quel moment une salle est libérée, et à quel moment une salle est occupée.

La logique de mon algorithme est donc la suivante :

• Je charge le fichier JSON et j'en extrais les sessions.
• Je crée une liste d'événements, dans laquelle, pour chaque session, j'ajoute l'événement "start" avec une valeur +1 (une salle est requise) et l'événement "end" avec une valeur -1 (une salle est libérée).
• Je trie cette liste selon les horaires.
• Je crée un compteur pour le nombre de salle en cours d'utilisation, et une variable qui enregistre le pic du nombre de salles.

Entrée JSON

[
  {
    "start": "09:00",
    "end": "10:00",
    "session_name": "Cours A",
    "teacher_name": "Prof A"
  },
  {
    "start": "09:30",
    "end": "10:30",
    "session_name": "Cours B",
    "teacher_name": "Prof B"
  },
  {
    "start": "10:00",
    "end": "11:00",
    "session_name": "Cours C",
    "teacher_name": "Prof C"
  },
  {
    "start": "09:30",
    "end": "11:00",
    "session_name": "Cours D",
    "teacher_name": "Prof D"
  }
]

Liste d'événements triée :

[("09:00", +1), ("09:30", +1), ("09:30", +1), ("10:00", +1), ("10:00", -1), ("10:30", -1), ("11:00", -1), ("11:00", -1)]

Calcul :

• 09:00 : +1 (1 salle occupée)
• 09:30 : +1 (2 salles)
• 09:30 : +1 (3 salles)
• 10:00 : +1 (4 salles, le pic est atteint)
• 10:00 : -1 (3 salles)
• 10:30 : -1 (2 salles)
• 11:00 : -1 (1 salle)
• 11:00 : -1 (0 salle)

Résultat final : 4 salles minimum sont nécessaires

1. load_sessions()

def load_sessions(file_path):
  with open(file_path, "r", encoding="utf-8") as file:
    return json.load(file)

Cette fonction lit un fichier JSON, et le charge avec json.load(file). Cette fonction a donc une complexité O(n), où n est le nombre de sessions dans le fichier.

Complexité totale : O(n)

2. create_events()

def create_events(sessions):
  events = []
  for session in sessions:
    events.append((session["start"], +1))
    events.append((session["end"], -1))
  return events

Cette fonction prend en entrée les sessions, qui sont au nombre de n. Pour chaque session, elle ajoute deux événements dans la liste events, la complexité de cette tâche est fixe, donc O(1).

Complexité totale : O(n)

3. calculate_rooms()

def calculate_rooms(events):
  events.sort(key=lambda x: (x[0], x[1]))
  number_rooms = 0
  max_rooms = 0
  for _, change in events:
    number_rooms += change
    max_rooms = max(max_rooms, number_rooms)
  return max_rooms

.sort() utilise Timsort, qui a une complexité de O(n log n) dans le pire des cas (source : https://fr.wikipedia.org/wiki/Timsort). On parcourt ensuite tous les éléments de events une seule fois. À chaque itération, on effectue des tâches de complexité O(1), puisque fixes.

Complexité totale : O(n log n)

4. main()

def main():
  if len(sys.argv) < 2:
    print("Erreur : veuillez fournir le chemin du fichier JSON en argument.")
    sys.exit(1)

  test_file = sys.argv[1]

  sessions = load_sessions(test_file)

  events = create_events(sessions)

  max_rooms = calculate_rooms(events)

  print(max_rooms)

La fonction main appelle les trois autres fonctions. La complexité globale est déterminée par l'opération la plus coûteuse, soit O(n log n).

Complexité finale : O(n log n)

Sources :

• https://www.sfeir.dev/front/comprendre-la-complexite-des-algorithmes/
• https://fr.wikipedia.org/wiki/Timsort
• https://www.youtube.com/watch?v=BgLTDT03QtU