借来保留队列:公平的预约
为什么重要 从零开始构建的预约系统,往往会奖励点击最快的人,或者让一个爽约的人挡住所有人。那些每天都要把稀缺的东西分给人们的地方,很久以前就选定了一种更好的设计。
三个柜台
一个图书馆的预约。你为一本已被借出的书办理了预约。当有一本还回来时,它会给预约队列中的第一个人,那个人会收到一条消息,有几天时间来取。如果他们没来,这本书就给下一个人,而第一个人会失去他们的位置。
一家带呼叫器的餐厅候位名单。你留下名字,拿到一个呼叫器。当一张桌子空出来时,下一组客人会被呼叫,他们有五分钟时间走到迎宾台,否则这张桌子就给下一组客人。
熟食柜台的号码牌。你拿一个号码。当叫到你的号码而你不在时,就叫下一个号码。你可以再拿一张新的号码牌,排到最后。
先比较,再写代码
- 在每一个例子中,你在队伍中的位置是什么时候确定的:在你提出请求时,还是在那样东西空出来时?
- 一个没有出现的人会怎样,他们有多长时间?
- 在等待有人来取的时候,那样东西会怎样?
- 用一句不提书、桌子或肉的话,说出共有的规则。
目标
移动团队共用一个小小的测试手机实验室。工程师们请求某个型号;当那个型号的一部手机空闲时,就会提供给他们,而他们必须在两小时内在实验室应用里认领它。一部被认领的手机会被预订一个八小时的时段,然后自动归还。如今,这个应用会把一部空闲的手机给最先按下“认领”的人,而人们已经开始写脚本去按它了。
stock = [("dev1", "pixel")]
events = [("request", 0, "ana", "pixel"), ("request", 5, "ben", "pixel"),
("claim", 10, "ben", "pixel"), ("claim", 30, "ana", "pixel")]
loans(stock, events) # -> [("ana", "dev1", 30)] (ben is not first)编写 loans(stock, events)。stock 列出 (device_id, model),在时间 0 时全部空闲。events 是 ("request", t, person, model) 或 ("claim", t, person, model),按时间 t(分钟)排序。规则如下:
- 每个型号都有一个按请求顺序排列的队列。如果那个人已经在这个型号的队列中,或者正持有这个型号的一个提供,那么这个请求会被忽略。
- 一部空闲的手机会提供给它的型号队列中的第一个人(他们会离开队列)。如果没有人在排队,它就在架子上等着,而之后对这个型号的请求会立刻得到它。如果架子上有好几部,就提供设备 ID 最小的那一部。
- 在时间
o发出的一个提供,在t < o + 120时可以被认领。一个对于那个人和型号没有有效提供的认领会被忽略。 - 在
o + 120时,一个未被认领的提供会失效,手机在那一刻再次空闲(规则 2)。 - 在时间
t的一次认领开始一次借用;手机在t + 480时空闲。 - 在一个事件的时间或之前到期的失效和归还,会在这个事件之前发生,按时间排序,然后按设备 ID 排序。
(person, device_id, claim_time) 的形式返回各次借用。
这个练习即将开放
完成它前面的那一课,这一课就会解锁。整门课程免费,无需账号,而且你现在就可以阅读这节课。
这个浏览器屏蔽了 learn.floati.life 的 Cookie,所以你在这里完成的课程无法按顺序打开。请允许这个网站使用 Cookie,然后重新加载。