新闻动态

有分数差异的限时任务怎样选择不冲突的组合:规则演算第18例

2026-11-18

同一时间只能执行一项任务时,尽量完成最多件,不一定能获得最高总分。一项较长但分数较高的任务,可能值得替换几项很短却分数不高的任务,选择目标必须先讲清楚。

本例采用的规则

本例每项任务有固定开始、结束时刻与正整数分数,不能移动或拆分。区间左闭右开,所以一项恰好结束时可以开始下一项。按结束时间排序,找到每项之前最后一个不冲突任务,再比较跳过当前项与选择当前项加上兼容前缀最优分数。

具体输入与记录

原记录为编号、开始、结束和分数。排序位置与原编号分别列出。

位置 | 编号 | 开始 | 结束 | 分数 | 兼容前驱位置 | 最优分数 | 选择编号 [0, 6, 1, 3, 5, -1, 5, [6]] [1, 3, 0, 6, 2, -1, 5, [6]] [2, 1, 5, 8, 18, 0, 23, [6, 1]] [3, 4, 5, 10, 8, 0, 23, [6, 1]] [4, 7, 9, 11, 14, 2, 37, [6, 1, 7]] [5, 0, 14, 15, 19, 4, 56, [6, 1, 7, 0]] [6, 8, 14, 15, 4, 4, 56, [6, 1, 7, 0]] [7, 5, 12, 16, 1, 4, 56, [6, 1, 7, 0]] [8, 2, 15, 17, 4, 6, 60, [6, 1, 7, 0, 2]] 最终总分60,所选任务[6, 1, 7, 0, 2]。

这些记录只描述本次输入。请先确认编号、时间或坐标的起点,再比较中间结果。空集合、数值零以及没有定义分别表达不同含义,不能任意互换。分数保持精确值,显示近似小数并不意味着计算过程按同样位数舍入。

如何独立复算

表格列出排序位置、原任务编号、兼容前驱和前缀最优总分;还原结果必须没有重叠,分数等于所选任务逐项相加。同分时本例优先跳过当前项,使输出保持稳定,其他同分合法组合也可能存在。

小规模复核可以枚举全部任务子集,剔除任何时间重叠的组合后比较总分。不要只按单位时长分数排序后贪心选择,因为时间位置同样影响相容性。把任务身份和排序下标分开,可避免回溯时选错原始任务。

适用范围

这里没有移动耗时、前置任务或执行成功概率,也不要求把时间全部排满。若任务允许调整开始时间,就不再是这组固定区间选择。目标是最大总分,并不保证选择件数最多或空闲时间最少。

复现时可以一次改变一个条件,观察结果从哪一行开始变化。出现差异应先核对规则,再检查输入和每一步状态,而不是直接把最终答案改成表中数字。把输入、边界约定和演算过程一起保存,才能在下一次调整后作出有意义的比较。