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