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