Barrido lineal para el solapamiento máximo
Cuente intervalos simultáneos mediante eventos
Barrido lineal para el solapamiento máximo es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 3 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.
La pregunta del solapamiento máximo
¿Cuántos intervalos cubren el mismo instante a la vez? El número máximo es el solapamiento máximo, el punto de mayor actividad de su línea temporal. 📈
Piense en eventos
Deje de pensar en intervalos completos. Divida cada uno en dos eventos: un +1 cuando comienza y un -1 cuando termina.
Construya la lista de eventos
Para cada intervalo, añada un evento de inicio y uno de final a una única lista compartida. Cada evento contiene una posición y un delta de más uno o menos uno.
events = []
for s, e in intervals:
events.append((s, 1)); events.append((e, -1))Ordene los eventos
Ordene cada evento por posición para poder recorrer la línea temporal de izquierda a derecha y procesar los cambios en el orden correcto.
events.sort()Recorra y cuente
Recorra los eventos ordenados manteniendo un contador acumulado. Añada cada delta al pasar por él; el contador indica cuántos intervalos están activos en ese momento.
active = 0
for pos, delta in events:
active += deltaSiga el máximo
Después de cada actualización, compare el contador con el mejor valor obtenido hasta el momento. El valor más grande que alcance el contador será el solapamiento máximo.
best = max(best, active)El truco para desempatar
Cuando las posiciones son iguales, el orden importa. Si un final en x debe liberar el espacio antes de un inicio en x, ordene los finales antes que los inicios en el mismo punto.
Codifique los deltas para ordenar correctamente
Una forma ingeniosa de resolver los empates es elegir los deltas de modo que la ordenación de tuplas lo haga por usted. Coloque el delta -1 antes que +1 cuando las posiciones coincidan.
events.append((s, 1)); events.append((e, -1)) # -1 sorts first at a tiePor qué es rápido
Usted crea 2n eventos, los ordena una vez y hace un recorrido una vez. El método completo es O(n log n), dominado por esa única ordenación.
Dónde aparece
El solapamiento máximo resuelve problemas clásicos, como calcular el número mínimo de salas necesarias para reuniones o el máximo de usuarios simultáneos en un servidor.
Más allá de contar
El mismo recorrido se puede ampliar fácilmente: calcule la longitud total cubierta o encuentre todas las posiciones donde cambia el recuento, todo en una sola pasada lineal.
Comprobación rápida
Hace un recorrido de los eventos para encontrar el solapamiento máximo.
Repaso
Convierta los intervalos en eventos de inicio +1 y de final -1, ordénelos y recorra un contador para encontrar el máximo. Resuelva los empates haciendo que los finales vayan antes que los inicios. 🚀
Preguntas frecuentes
¿La lección «Barrido lineal para el solapamiento máximo» es gratis?
Sí — el texto completo de «Barrido lineal para el solapamiento máximo» 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 «Barrido lineal para el solapamiento máximo»?
Cuente intervalos simultáneos mediante eventos 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 3 de 4.
¿Cuánto tiempo toma la lección «Barrido lineal para el solapamiento máximo»?
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
- Ordene intervalos por inicio
- Combine intervalos superpuestos
- Barrido lineal para el solapamiento máximo
- Mínimas eliminaciones para evitar solapamientos