间隔调度算法几乎基于按结束时间对作业进行排序，但是如果调度作业 A 意味着您必须调度作业 C，该怎么办？
例如，假设您正在尝试安排广播节目，节目 A 在周一上午 10 点至上午 11 点和下午 2 点至下午 3 点播放，但节目 B 在周一 1:30-2:30 播放？你不能只运行程序 A 的 10-11 部分。要么全有，要么全无。或者，假设该程序在周一、周三、周五运行，但每天的时间不同。
我玩过的想法：
最短路径算法，您可以同时遍历一周中的每一天的 7 个图形，每个图形进行排序以仅连接后面的程序。如果您在星期一选择程序 A，则您在所有日子都选择它，以此类推。如果程序需要在一天内运行两次，则此解决方案无法解决问题。
为 n 个程序生成 n × n 矩阵并检查每个程序与其他程序的兼容性。遍历一个图，其中每个程序仅与非冲突程序连接。有点坚持这个想法并完全寻找下一步或新想法。
我刚刚在CS Stack Exchange上重新问了这个问题，因为这个问题很旧，并且接受的答案中的等效性有点脆弱。在这里重新发布我的答案以获得更高的知名度：
这相当于最大加权独立集问题——给定一个带有加权顶点的图，找到一个顶点子集，使得该子集中没有两个顶点在图中相邻，并且它们的权重之和被最大化。
解决问题的图是一种区间图，其中每个顶点代表一组相关区间，其权重是区间权重的总和。如果两个顶点的一个或多个间隔重叠，则在两个顶点之间绘制一条边。
我还没有确定这个公式是否易于处理。虽然这个问题是 NP-hard 问题，但我们知道对于某些类型的图可以有效地解决它，包括区间图，其中每个顶点代表一个区间。有关已知算法，请参阅独立集维基百科页面。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句