游戏知识实验课:共享工位预约的峰值占用量——容量9下的九条工位预约(练习23)
多条预约时间段叠在一起时,总需求最高的时刻未必是某条最长预约期间。把所有起止点作为变化边界,可以核对何时超出可用工位数量。
本篇用一组独立输入把规则展开为可重复核对的记录。先确认单位、编号及边界,再自行尝试推演,然后寻找与下面过程第一次不同的位置。所有结果只在这里写明的规则下成立,不能当作所有游戏的统一实现。
规则与输入
每条预约给出整数开始、结束及所需数量,开始包含、结束排除。每个边界时刻先移除到期预约再计入新预约;在相邻边界之间用量保持,比较固定容量并找出峰值及超量区间。
每条[开始,结束,需求] [[2, 8, 3], [12, 18, 3], [5, 7, 3], [15, 18, 4], [1, 3, 3], [10, 13, 2], [2, 7, 1], [2, 10, 3], [2, 9, 4]] 容量9
逐步推演
边界时刻1,有效预约编号[4],总占用3,容量9,容量内。
边界时刻2,有效预约编号[0, 4, 6, 7, 8],总占用14,容量9,超量。
边界时刻3,有效预约编号[0, 6, 7, 8],总占用11,容量9,超量。
边界时刻5,有效预约编号[0, 2, 6, 7, 8],总占用14,容量9,超量。
边界时刻7,有效预约编号[0, 7, 8],总占用10,容量9,超量。
边界时刻8,有效预约编号[7, 8],总占用7,容量9,容量内。
边界时刻9,有效预约编号[7],总占用3,容量9,容量内。
边界时刻10,有效预约编号[5],总占用2,容量9,容量内。
边界时刻12,有效预约编号[1, 5],总占用5,容量9,容量内。
边界时刻13,有效预约编号[1],总占用3,容量9,容量内。
边界时刻15,有效预约编号[1, 3],总占用7,容量9,容量内。
边界时刻18,有效预约编号[],总占用0,容量9,容量内。
峰值占用14,超量区间[起,止,超出量]为[[2, 3, 5], [3, 5, 2], [5, 7, 5], [7, 8, 1]]。
怎样独立检查
逐个整数拍直接列出仍生效的预约并求和,与边界扫描得到的值比较。因为本例所有边界都是整数且段内恒定,这样能独立覆盖全部变化,不遗漏同刻结束和开始的交接。
预约只是虚构工位资源,不涉及真实付款或人员排班。超量表示这组计划不能同时满足,本例只报告冲突而不自动删掉任何预约。若时间可以是任意分数,按整数拍枚举就不再足以验证所有区间。
练习时先保存原始输入及中间结果,再只改变一个条件观察差异。重点检查空状态、相同数值、恰好到达边界和最后一步。不要为了凑出相同的最终结果而忽略较早出现的偏差,过程和结论都应能由同一套规则解释。
