Programma Les 140 van 148 · Tien deuren en de veldkit
Tien deuren en de veldkit

Laatste 2: een venster voor elke server

AI uit Dit is een eindexamen, gekoppeld aan het basislijn examen dat je deed in de eerste module: dezelfde vaardigheid op een ander probleem van dezelfde moeilijkheidsgraad, dus lees de regels opnieuw (je basislijn code wordt niet overgenomen). De tutor staat uit en er zijn geen hints. Werk alleen. De cursus vergelijkt dit met je basislijn in de volgende les.

Een operations team heeft een venster nodig wanneer elke server in een cluster niet wordt gebruikt, om ze samen te patchen. Het archief van elke server legt de vensters vast wanneer het niet werd gebruikt, en het archief brengt kosten in rekening voor elke opgehaalde invoer. De archieven gaan jaren terug.

een klein voorbeeld

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)
Jij bent aan de beurt

Schrijf maintenance_window(servers, after, length). servers is een lijst van Tapes, één per server. Elke houdt de idle vensters van die server als (start, end) minutenparen, gesorteerd op start, nooit overlappend of tegen elkaar aan (tussen twee vensters is de server bezet). Een venster is idle van start tot maar niet inclusief end, en het laatste venster van elke server eindigt bij 10**9, dus is er altijd een antwoord. Geef de vroegste minuut t >= after terug zodanig dat elke server voor de hele [t, t + length).
Budget: 50 servers met ongeveer 2.000 vensters elk (ongeveer 100.000 items), en after is meestal maanden in de data. Eén zoekopdracht kan maximaal 10.000 items in totaal lezen. len() van een Tape is gratis. Een Tape gedraagt zich als een read-only lijst (indexeren, slicen en een lus werken allemaal), en elk item dat het je geeft telt als één leesactie.

AI uit: geen tutor, hints of uitgewerkte oplossing voor deze. Alleen je eigen denkwerk.

Een probleem ontdekt in deze les? Meld het · Vraag naar deze les

Deze oefening opent binnenkort

Maak de les ervoor af voordat deze wordt ontgrendeld. De hele cursus is gratis, geen account nodig, en je kunt deze les nu lezen.