Saltar al contenido

Intervalos: fundamentos y ordenamiento

Lección 1 de 4 · 4 min

Intervalos: fundamentos y ordenamiento

Paso 1 de 8

Cuatro reuniones, dibujadas en el orden en que se reservaron. Cada una es solo un inicio y un fin.

La idea

Un intervalo es solo un par: inicio y fin. Dos intervalos se superponen cuando cada uno empieza antes de que el otro termine: una sola prueba, sin casos especiales.

Revisar cada par cuesta n al cuadrado. El ordenamiento (sorting) por inicio cuesta n log n y luego garantiza algo útil: cada intervalo que encuentres después empieza en el que tienes o más tarde.

Ejemplo del mundo real

Un calendario compartido dibujado de izquierda a derecha a lo largo del día. Nadie compara la cuarta reunión del martes con la primera: los choques se ven porque las barras están dispuestas en orden de tiempo, que es justo lo que hace ordenar por inicio.

El código

Te toca

¿Qué imprime esto?

spans = [(5, 8), (1, 4), (1, 2)]
spans.sort()
print(spans[0])

Mini quiz

1 / 3

Dos intervalos a y b se superponen cuando: