Temario Lección 140 de 148 · Diez puertas y el kit de campo
Diez puertas y el kit de campo

Final 2: una ventana para cada servidor

IA apagada Este es un examen final, emparejado con el examen de referencia que hiciste en el primer módulo: la misma habilidad en un problema distinto de la misma dificultad, así que lee sus reglas desde cero (tu código de referencia no te servirá). El tutor está apagado y no hay pistas. Trabaja solo. El curso lo compara con tu examen de referencia en la siguiente lección.

Un equipo de operaciones necesita una ventana en la que todos los servidores de un clúster estén inactivos, para aplicarles parches a la vez. El archivo de cada servidor registra las ventanas en las que estuvo inactivo, y el archivo cobra por cada entrada que se trae. Los archivos se remontan años atrás.

Un ejemplo pequeño

from creative.budget import Tape
idle = [[(0, 10), (30, 60), (90, 10**9)],     # server A
        [(0, 40), (50, 10**9)],               # server B
        [(20, 10**9)]]                        # server C
maintenance_window([Tape(s) for s in idle], 0, 10)   # -> 30  (A and B idle from 30 to 40, C from 20)
maintenance_window([Tape(s) for s in idle], 0, 15)   # -> 90  (B is busy from 40 to 50, A from 60 to 90)
maintenance_window([Tape(s) for s in idle], 55, 5)   # -> 55  (55 + 5 = 60: touching the end is fine)
Tu turno

Escribe maintenance_window(servers, after, length). servers es una lista de Tapes, una por servidor. Cada una guarda las ventanas inactivas de ese servidor como parejas de minutos (start, end), ordenadas por start, sin solaparse ni tocarse nunca (entre dos ventanas el servidor está ocupado). Una ventana está inactiva desde start hasta end, sin incluirlo, y la última ventana de cada servidor termina en 10**9, así que siempre hay respuesta. Devuelve el minuto más temprano t >= after tal que todos los servidores estén inactivos durante todo [t, t + length).
Presupuesto: 50 servidores con unas 2,000 ventanas cada uno (unas 100,000 entradas), y after suele estar meses dentro de los datos. Una búsqueda puede leer como mucho 10,000 entradas en total. len() de una Tape es gratis. Una Tape se comporta como una lista de solo lectura (funcionan el índice, las porciones y los bucles), y cada entrada que te da cuenta como una lectura.

IA desactivada: en este no hay tutor, pistas ni solución. Solo tu propio razonamiento.

¿Has visto un problema en esta lección? Avísanos · Preguntar sobre esta lección

Este ejercicio se abre pronto

Termina la lección anterior y esta se desbloquea. Todo el curso es gratis, no hace falta cuenta, y puedes leer esta lección ahora mismo.