Planificación y fusión de intervalos
Resuelva meeting-rooms y non-overlapping-intervals ordenando por hora de finalización, y merge-intervals ordenando por hora de inicio.
Planificación y fusión de intervalos es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 2 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
Introducción a los problemas de intervalos
Los problemas de intervalos aparecen constantemente en entrevistas sobre planificación, gestión de calendarios y asignación de recursos. Los patrones clave son: combinar intervalos solapados, contar el número mínimo de salas de reuniones, encontrar el conjunto máximo de intervalos no solapados e insertar un intervalo nuevo. La mayoría de los problemas de intervalos comienzan con el mismo paso: ordenar los intervalos por tiempo de inicio (o por tiempo de finalización, según el problema). Elegir correctamente la clave de ordenación suele ser la parte más difícil.
# 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')Combinar intervalos solapados
Merge Intervals (LeetCode 56): dada una lista de intervalos, combine todos los que se solapen. Algoritmo: ordene por tiempo de inicio. Recorra la lista ordenada; si el intervalo actual se solapa con el último intervalo combinado (su inicio ≤ el último final), extienda el final del último intervalo combinado hasta el máximo de ambos finales. En caso contrario, añada el intervalo actual como un nuevo intervalo combinado. Tiempo: O(n log n) para la ordenación y O(n) para la combinación.
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)Insertar un intervalo
Insert Interval (LeetCode 57): dada una lista ordenada de intervalos no solapados, inserte un intervalo nuevo y vuelva a combinarlos. Recorra la lista en tres fases: (1) añada todos los intervalos que terminan antes de que comience el intervalo nuevo; (2) combine todos los intervalos que se solapan con el intervalo nuevo (amplíe sus límites); (3) añada todos los intervalos restantes. Es un único recorrido O(n) después de la ordenación O(n log n) (que ya se ha realizado en este problema).
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]]Salas de reuniones I: ¿puede asistir a todas?
Meeting Rooms I (LeetCode 252): dados los intervalos horarios de varias reuniones, determine si una persona puede asistir a todas. Ordene por tiempo de inicio; si alguna reunión comienza antes de que termine la anterior, se solapan. Esta es la comprobación de intervalos más sencilla: O(n log n) en total. La idea clave es que, después de ordenar, solo necesita comparar pares consecutivos.
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)Salas de reuniones II: número mínimo de salas
Meeting Rooms II (LeetCode 253): encuentre el número mínimo de salas de conferencias necesarias para celebrar todas las reuniones simultáneamente. Utilice un min-heap para realizar un seguimiento de la sala que termina antes. Ordene las reuniones por tiempo de inicio. Para cada reunión nueva: si comienza después de la hora de finalización de la sala que termina antes, reutilice esa sala (extraiga y añada de nuevo). En caso contrario, abra una sala nueva. El tamaño del heap al final equivale al número de salas necesarias.
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]])) # 2Alternativa de línea de barrido para contar salas
Un enfoque alternativo O(n log n): la línea de barrido. Cree eventos para el inicio (+1) y el final (-1) de cada intervalo. Ordene todos los eventos por tiempo (en caso de empate: coloque el final antes que el inicio si desea intervalos no inclusivos). Recorra de izquierda a derecha manteniendo un recuento acumulado de las reuniones activas. El recuento máximo es el número mínimo de salas necesarias. Este enfoque resulta más intuitivo para algunas personas y se generaliza a otros problemas de conteo sobre intervalos.
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)Intervalos no solapados: selección máxima
Non-Overlapping Intervals (LeetCode 435): encuentre el número mínimo de intervalos que debe eliminar para que los restantes no se solapen. Esto equivale a encontrar el número máximo de intervalos no solapados (selección de actividades) y devolver el resto como eliminaciones. Ordene por tiempo de finalización: conserve de forma voraz el intervalo que termina antes (maximiza el espacio para los intervalos posteriores). Cuando el siguiente intervalo se solape, descártelo (cuente una eliminación).
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)¿Por qué ordenar por hora de finalización y no por hora de inicio?
Para la selección de actividades (conjunto máximo de actividades no solapadas), ordenar por hora de finalización es óptimo de forma demostrable. La intuición es que una actividad que termina pronto deja más espacio para actividades futuras. Si ordenamos por hora de inicio, podríamos elegir una actividad muy larga que comienza pronto y bloquea muchas actividades posteriores más cortas. Argumento de intercambio: si la solución óptima elige la actividad A en lugar de G, que es la que termina antes, sustituya A por G; G no termina más tarde, por lo que no entra en conflicto con ninguna actividad con la que A no entrara en conflicto.
# 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) # 2Intersecciones de listas de intervalos
Intersecciones de listas de intervalos (LeetCode 986): encuentre todos los pares que se intersectan a partir de dos listas de intervalos ordenadas. Utilice un enfoque de dos punteros. En cada paso, calcule la intersección del par actual (el máximo de los inicios y el mínimo de los finales). Si inicio ≤ fin, la intersección es válida. Después, avance el puntero del intervalo que termine primero. Complejidad temporal 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]]Partición de etiquetas
Partición de etiquetas (LeetCode 763): particione una cadena en tantas partes como sea posible, de modo que cada carácter aparezca como máximo en una parte. Enfoque greedy: para cada carácter, encuentre su última aparición. Recorra la cadena manteniendo un max_end. Cuando i == max_end, la partición actual está completa: registre su longitud y comience una nueva partición. Este es un problema de fusión de intervalos disfrazado.
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'Resumen de problemas de intervalos
Domine estos cuatro patrones para los intervalos: (1) Fusionar: ordenar por inicio y extender el último si hay solapamiento. (2) Contar salas: ordenar por inicio y utilizar un min-heap de horas de finalización. (3) Máximo conjunto no solapado: ordenar por finalización y seleccionar de forma greedy. (4) Insertar: recorrido lineal en tres fases. La clave de ordenación es importante: la fusión utiliza el inicio, mientras que la selección máxima utiliza la finalización. La complejidad temporal siempre es O(n log n), dominada por la ordenación; la fusión y el recorrido son 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')Comprobación rápida
Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Resumen de la lección
En esta lección ha aprendido: fusionar intervalos ordenándolos por inicio y extendiendo el último intervalo cuando se produce un solapamiento, el número mínimo de salas de reuniones se obtiene ordenando por inicio y utilizando un min-heap de horas de finalización, reutilizando las salas cuando la que termina antes queda libre, y los intervalos máximos no solapados se obtienen mediante una selección greedy ordenada por hora de finalización. A continuación abordaremos Juego de saltos I y II: problemas de alcanzabilidad y de número mínimo de saltos resueltos mediante la expansión greedy de rangos.
Preguntas frecuentes
¿La lección «Planificación y fusión de intervalos» es gratis?
Sí — el texto completo de «Planificación y fusión de intervalos» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Planificación y fusión de intervalos»?
Resuelva meeting-rooms y non-overlapping-intervals ordenando por hora de finalización, y merge-intervals ordenando por hora de inicio. Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 2 de 4.
¿Cuánto tiempo toma la lección «Planificación y fusión de intervalos»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Voraces frente a PD: cuándo usar cada enfoque
- Planificación y fusión de intervalos
- Jump Game I y II
- Task Scheduler y Gas Station