公司新闻

挑选互不重叠的短片段时为什么先结束更有用:规则练习第11例

2026-11-09

从一组时间片段中选择尽量多的片段时,最早开始或持续时间最短都未必给后续留下最合适的空间。一个明确的选择规则是优先考虑最早结束的片段。

所有片段都是左闭右开的区间,结束时刻等于下一段开始时刻可以相接。按结束时刻、开始时刻、编号排序,只有当前片段的开始不早于上一已选片段的结束才接受。

本例输入与约定

十二个片段的开始和结束时刻为[[3, 11], [2, 12], [13, 17], [0, 7], [19, 20], [20, 21], [3, 8], [10, 19], [12, 22], [7, 12], [7, 16], [24, 31]]。

完整计算记录

考虑编号 | 片段范围 | 上次接受段的终点(初始为-1) | 接受 3 | [0, 7] | -1 | True 6 | [3, 8] | 7 | False 0 | [3, 11] | 7 | False 1 | [2, 12] | 7 | False 9 | [7, 12] | 7 | True 10 | [7, 16] | 12 | False 2 | [13, 17] | 12 | True 7 | [10, 19] | 17 | False 4 | [19, 20] | 17 | True 5 | [20, 21] | 20 | True 8 | [12, 22] | 21 | False 11 | [24, 31] | 21 | True 最终接受6段,编号按播放顺序为[3, 9, 2, 4, 5, 11]。

表中编号仅用于识别本例的元素。读取一个结果时,应先核对它对应的输入、处理顺序和边界约定;布尔值表示条件是否成立,空集合表示没有符合要求的对象,不应把这些字段混成同一种数值。

复核方法与适用范围

本例目标是片段数量最多,不是总播放长度最长,也没有片段权重。对十二个片段可以穷举所有子集,核对是否存在更多个互不重叠的片段,独立验证贪心结果。

如果片段之间需要额外过渡时间,或某些片段必须一起出现,原来的选择规则就不再直接适用。选择数量相同的方案可能有多种,不能要求所有正确方案的编号完全相同。

练习时可以先独立计算最前面的一步,再检查最后的整体不变量。若结论不同,应保留各步记录,定位第一处差异;只调整最终数字会掩盖规则理解上的问题。改变输入后也要重新演算,而不是照抄这一例的输出。