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