课程大纲 第 140 课,共 148 课 · 十扇门和 Field Kit
十扇门和 Field Kit

期末 2:一个适合每台服务器的窗口

关闭 AI 这是一场期末考试,和你在第一个模块中做的基线考试一一对应:同样的技能,换了一道难度相同的不同题目,所以要重新阅读它的规则(你的基线代码不会适用)。导师已经关闭,也没有提示。独自完成。课程会在下一课把它和你的基线排在一起。

一个运维团队需要一个集群中每台服务器都空闲的窗口,以便一起给它们打补丁。每台服务器的归档记录着它空闲的那些窗口,而归档会为每一个被取回的条目收费。归档可以追溯到好几年前。

一个小例子

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)
轮到你了

编写 maintenance_window(servers, after, length)。servers 是一个由 Tape 组成的列表,每台服务器一个。每个 Tape 以按开始时间排序的 (start, end) 分钟对保存那台服务器的空闲窗口,这些窗口永远不会重叠或相接(在两个窗口之间,服务器是忙碌的)。一个窗口从 start 开始空闲,直到 end 为止但不包括它,而每台服务器的最后一个窗口都在 10**9 结束,所以总会有一个答案。返回最早的分钟 t >= after,使得每台服务器在整个 [t, t + length) 期间都是空闲的。
预算:50 台服务器,每台大约 2,000 个窗口(大约 100,000 个条目),而 after 通常位于数据中好几个月之后。一次搜索总共最多只能读取 10,000 个条目。Tape 的 len() 是免费的。Tape 的行为就像一个只读的列表(索引、切片和循环都能用),它交给你的每一个条目都算作一次读取。

关闭 AI:这一题没有导师、提示或参考答案。只靠你自己的思考。

发现这节课有问题?报告它 · 就这节课提问

这个练习即将开放

完成它前面的那一课,这一课就会解锁。整门课程免费,无需账号,而且你现在就可以阅读这节课。