Planification et fusion d’intervalles
Résolvez meeting-rooms et non-overlapping-intervals en triant selon l’heure de fin, puis merge-intervals en triant selon l’heure de début.
Planification et fusion d’intervalles est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 2 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
Vue d’ensemble des problèmes d’intervalles
Les problèmes d’intervalles apparaissent constamment lors des entretiens portant sur la planification, la gestion des calendriers et l’allocation des ressources. Les principaux schémas sont les suivants : fusionner les intervalles qui se chevauchent, compter le nombre minimal de salles de réunion, trouver l’ensemble maximal d’intervalles non chevauchants et insérer un nouvel intervalle. La plupart des problèmes d’intervalles commencent par la même étape : sort les intervalles selon leur heure de début (ou selon leur heure de fin, en fonction du problème). Choisir la bonne clé de tri est souvent la partie la plus difficile.
# Intervals: each = [start, end] (inclusive or exclusive by problem)
# Example:
intervals = [[1,3],[2,6],[8,10],[15,18]]
# Sorted by start (already sorted here)
# Visually:
# [1,3] |-|
# [2,6] |---|
# [8,10] |--|
# [15,18] |---|
print('Intervals ready for analysis')Fusionner les intervalles qui se chevauchent
Fusionner les intervalles (LeetCode 56) : étant donnée une liste d’intervalles, fusionnez tous ceux qui se chevauchent. Algorithme : sort selon l’heure de début. Parcourez la liste triée ; si l’intervalle courant chevauche le dernier intervalle fusionné (son début ≤ la valeur end du dernier intervalle fusionné), étendez la valeur end du dernier intervalle fusionné au maximum des deux valeurs end. Sinon, utilisez append pour ajouter l’intervalle courant comme nouvel intervalle fusionné. Durée : O(n log n) pour le tri, puis O(n) pour la fusion.
def merge_intervals(intervals):
intervals.sort(key=lambda x: x[0]) # sort by start
merged = [intervals[0]]
for start, end in intervals[1:]:
last_end = merged[-1][1]
if start <= last_end:
# Overlapping: extend the last interval
merged[-1][1] = max(last_end, end)
else:
# Non-overlapping: add as new interval
merged.append([start, end])
return merged
print(merge_intervals([[1,3],[2,6],[8,10],[15,18]]))
# [[1,6],[8,10],[15,18]]
print(merge_intervals([[1,4],[4,5]]))
# [[1,5]] (touching intervals merge)Insérer un intervalle
Insérer un intervalle (LeetCode 57) : étant donnée une liste triée et non chevauchante, insérez un nouvel intervalle, puis effectuez une nouvelle fusion. Parcourez la liste en trois phases : (1) ajoutez tous les intervalles dont end précède le début du nouvel intervalle ; (2) fusionnez tous les intervalles qui chevauchent le nouvel intervalle (élargissez ses bornes) ; (3) ajoutez tous les intervalles restants. Il s’agit d’un seul parcours en O(n) après le tri en O(n log n), déjà effectué dans ce problème.
def insert_interval(intervals, new_interval):
result = []
i = 0
n = len(intervals)
# Phase 1: intervals before new_interval
while i < n and intervals[i][1] < new_interval[0]:
result.append(intervals[i])
i += 1
# Phase 2: merge overlapping intervals
while i < n and intervals[i][0] <= new_interval[1]:
new_interval[0] = min(new_interval[0], intervals[i][0])
new_interval[1] = max(new_interval[1], intervals[i][1])
i += 1
result.append(new_interval)
# Phase 3: remaining intervals
while i < n:
result.append(intervals[i])
i += 1
return result
print(insert_interval([[1,3],[6,9]], [2,5])) # [[1,5],[6,9]]
print(insert_interval([[1,2],[3,5],[6,7],[8,10],[12,16]], [4,8]))
# [[1,2],[3,10],[12,16]]Salles de réunion I : pouvez-vous toutes les suivre ?
Salles de réunion I (LeetCode 252) : étant donnés les intervalles de time des réunions, déterminez si une personne peut assister à toutes les réunions. Triez selon l’heure de début ; si une réunion commence avant la fin de la précédente, elles se chevauchent. Il s’agit de la vérification d’intervalles la plus simple, en O(n log n) au total. L’idée essentielle est qu’après le tri, il suffit de comparer les paires consécutives.
def can_attend_meetings(intervals):
intervals.sort(key=lambda x: x[0])
for i in range(1, len(intervals)):
# Current meeting starts before previous ends?
if intervals[i][0] < intervals[i-1][1]:
return False
return True
print(can_attend_meetings([[0,30],[5,10],[15,20]])) # False (0,30 overlaps 5,10)
print(can_attend_meetings([[7,10],[2,4]])) # True (4 < 7, no overlap)Salles de réunion II : nombre minimal de salles
Salles de réunion II (LeetCode 253) : trouvez le nombre minimal de salles de conférence nécessaires pour tenir toutes les réunions simultanément. Utilisez un tas-minimal pour suivre la salle dont la valeur end time est la plus précoce. Triez les réunions selon leur heure de début. Pour chaque nouvelle réunion : si elle commence après le end time de la salle qui se libère le plus tôt, réutilisez cette salle (pop, puis ajoutez-la). Sinon, ouvrez une nouvelle salle. La taille du tas à la fin correspond au nombre de salles nécessaires.
import heapq
def min_meeting_rooms(intervals):
if not intervals: return 0
intervals.sort(key=lambda x: x[0]) # sort by start
heap = [] # min-heap of end times
for start, end in intervals:
if heap and heap[0] <= start:
heapq.heapreplace(heap, end) # reuse earliest-ending room
else:
heapq.heappush(heap, end) # open a new room
return len(heap)
print(min_meeting_rooms([[0,30],[5,10],[15,20]])) # 2
print(min_meeting_rooms([[7,10],[2,4]])) # 1
print(min_meeting_rooms([[9,10],[4,9],[4,17]])) # 2Approche par balayage pour compter les salles
Une autre approche en O(n log n) consiste à utiliser une ligne de balayage. Créez un événement pour chaque début d’intervalle (+1) et chaque end (-1). Triez tous les événements selon time (en cas d’égalité : end avant le début si vous souhaitez des bornes non inclusives). Balayez de gauche à droite en maintenant le nombre courant de réunions actives. Le nombre maximal correspond au nombre minimal de salles nécessaires. Cette approche est plus intuitive pour certaines personnes et se généralise à d’autres problèmes de comptage sur les intervalles.
def min_rooms_sweep(intervals):
events = []
for start, end in intervals:
events.append((start, 1)) # meeting starts
events.append((end, -1)) # meeting ends
# Sort: same time → end (-1) before start (1) if exclusive
events.sort(key=lambda x: (x[0], x[1]))
max_rooms = current = 0
for _, delta in events:
current += delta
max_rooms = max(max_rooms, current)
return max_rooms
print(min_rooms_sweep([[0,30],[5,10],[15,20]])) # 2
print(min_rooms_sweep([[1,5],[2,6],[3,7]])) # 3 (all overlap at t=3)Intervalles non chevauchants : sélection maximale
Intervalles non chevauchants (LeetCode 435) : trouvez le nombre minimal d’intervalles à remove pour que les autres ne se chevauchent pas. Cela revient à trouver le nombre maximal d’intervalles non chevauchants (sélection d’activités), puis à retourner les autres comme suppressions. Triez selon l’heure de fin : conservez de manière gloutonne l’intervalle qui se termine le plus tôt (ce qui maximise la place pour les intervalles suivants). Lorsque l’intervalle suivant chevauche celui-ci, utilisez discard (comptez une suppression).
def erase_overlap_intervals(intervals):
if not intervals: return 0
intervals.sort(key=lambda x: x[1]) # sort by END time
removals = 0
last_end = float('-inf')
for start, end in intervals:
if start >= last_end:
last_end = end # keep this interval
else:
removals += 1 # remove this interval (it overlaps)
return removals
print(erase_overlap_intervals([[1,2],[2,3],[3,4],[1,3]])) # 1 (remove [1,3])
print(erase_overlap_intervals([[1,2],[1,2],[1,2]])) # 2
print(erase_overlap_intervals([[1,2],[2,3]])) # 0 (no overlap)Pourquoi trier par heure de fin plutôt que par heure de début ?
Pour la sélection d’activités (ensemble maximal sans chevauchement), trier par heure de fin est optimal, comme on peut le démontrer. Intuition : une activité qui se termine tôt laisse davantage de place aux activités suivantes. Si nous trions par heure de début, nous pouvons choisir une activité très longue qui commence tôt et qui bloque de nombreuses activités plus courtes commençant plus tard. Argument d’échange : si la solution optimale choisit l’activité A plutôt que G, qui se termine le plus tôt, remplaçons A par G — G ne se termine pas plus tard, donc elle n’entre en conflit avec aucune activité avec laquelle A n’entrait pas déjà en conflit.
# Counterexample for sorting by START time:
# [[1,10],[2,3],[4,5]] — sorted by start: [1,10],[2,3],[4,5]
# Sort-by-start greedy keeps [1,10], can't add [2,3] or [4,5] (all overlap [1,10])
# Selects: 1 interval
# Sort-by-end greedy:
# [[2,3],[4,5],[1,10]] — sorted by end
# Keep [2,3] (end=3), then [4,5] (start=4 >= 3, keep), then [1,10] (start=1 < 5, skip)
# Selects: 2 intervals — OPTIMAL
intervals = [[1,10],[2,3],[4,5]]
intervals.sort(key=lambda x: x[1])
last_end = float('-inf')
count = 0
for s, e in intervals:
if s >= last_end:
count += 1; last_end = e
print('Max non-overlapping:', count) # 2Intersections de listes d’intervalles
Intersections de listes d’intervalles (LeetCode 986) : trouvez toutes les paires qui s’intersectent dans deux listes d’intervalles triées. Utilisez une approche à deux pointeurs. À chaque étape, calculez l’intersection de la paire actuelle (le maximum des débuts et le minimum des fins). Si le début ≤ la fin, l’intersection est valide. Avancez ensuite le pointeur de l’intervalle qui se termine le premier. Complexité temporelle : O(m+n).
def interval_intersection(A, B):
result = []
i = j = 0
while i < len(A) and j < len(B):
# Intersection boundaries
lo = max(A[i][0], B[j][0])
hi = min(A[i][1], B[j][1])
if lo <= hi:
result.append([lo, hi]) # valid intersection
# Advance pointer of interval that ends first
if A[i][1] < B[j][1]:
i += 1
else:
j += 1
return result
A = [[0,2],[5,10],[13,23],[24,25]]
B = [[1,5],[8,12],[15,24],[25,26]]
print(interval_intersection(A, B))
# [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]Étiquettes de partition
Étiquettes de partition (LeetCode 763) : partitionnez une chaîne en autant de parties que possible de sorte que chaque caractère apparaisse dans au plus une partie. Approche gloutonne : pour chaque caractère, trouvez sa dernière occurrence. Parcourez la chaîne en maintenant un max_end. Lorsque i == max_end, la partition actuelle est terminée — enregistrez sa longueur et commencez une nouvelle partition. Il s’agit en réalité d’un problème de fusion d’intervalles.
def partition_labels(s):
last = {c: i for i, c in enumerate(s)} # last occurrence of each char
partitions = []
start = max_end = 0
for i, c in enumerate(s):
max_end = max(max_end, last[c])
if i == max_end: # partition complete
partitions.append(max_end - start + 1)
start = i + 1
return partitions
print(partition_labels('ababcbacadefegdehijhklij'))
# [9, 7, 8] — parts 'ababcbaca', 'defegde', 'hijhklij'Résumé des problèmes d’intervalles
Maîtrisez ces quatre schémas pour les intervalles : (1) Fusionner : trier par début, puis étendre le dernier intervalle en cas de chevauchement. (2) Compter les salles : trier par début et utiliser un tas-min des heures de fin. (3) Maximiser le nombre d’intervalles sans chevauchement : trier par fin et effectuer une sélection gloutonne. (4) Insérer : effectuer un parcours linéaire en trois phases. La clé de tri est importante : la fusion utilise le début, tandis que la sélection maximale utilise la fin. La complexité temporelle est toujours O(n log n), dominée par le tri ; la fusion et le parcours sont en O(n).
# Quick reference:
# Merge intervals: sort by start, extend if overlap
# Insert interval: three-phase linear scan
# Meeting rooms (can?): sort by start, check consecutive overlap
# Meeting rooms (min?): sort by start, min-heap of end times / sweep
# Max non-overlapping: sort by END, greedy keep
# Min removals: n - max_non_overlapping
# Interval intersection: two pointers on sorted lists
print('Pattern: sort key is the decisive choice')
print('Merge → sort by start')
print('Activity selection → sort by end')
print('Room count → sort by start + heap of ends')Vérification rapide
Évaluez votre compréhension des concepts de Structures de données et algorithmes — Préparation aux entretiens de programmation présentés dans cette leçon.
Récapitulatif de la leçon
Dans cette leçon, vous avez appris à : fusionner des intervalles en les triant par début et en étendant le dernier intervalle lorsqu’un chevauchement se produit, déterminer le nombre minimal de salles de réunion en triant par début et en utilisant un tas-min des heures de fin, afin de réutiliser les salles dès que celle qui se termine le plus tôt est libre, et sélectionner gloutonnement le nombre maximal d’intervalles sans chevauchement en les triant par heure de fin. Nous allons maintenant aborder Jeu de sauts I et II — des problèmes d’accessibilité et de nombre minimal de sauts résolus par extension gloutonne de la portée.
Questions Fréquemment Posées
La leçon « Planification et fusion d’intervalles » est-elle gratuite ?
Oui — le texte complet de « Planification et fusion d’intervalles » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Planification et fusion d’intervalles » ?
Résolvez meeting-rooms et non-overlapping-intervals en triant selon l’heure de fin, puis merge-intervals en triant selon l’heure de début. Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 2 sur 4.
Combien de temps prend la leçon « Planification et fusion d’intervalles » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?
Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Glouton ou DP : quand utiliser chaque approche
- Planification et fusion d’intervalles
- Jeu des sauts I et II
- Planificateur de tâches et station-service