在间隔调度中，算法是选择最早完成时间。但在间隔着色中，前者不起作用。是否有示例或解释为什么选择最早完成时间不适用于间隔着色？
区间着色问题是：给定一组区间，我们想要着色
所有间隔，以便给定相同颜色的间隔不相交，目标是尽量减少使用的颜色数量。这可以被认为是区间划分问题（如果它更有意义的话）
我指的间隔调度问题是：如果你去一个主题公园，有很多演出，每个演出的起止时间就是一个间隔，你就是资源。您想参加尽可能多的演出。
这只是一个尝试图片直到找到示例的情况。我画的第一张图显示了问题的分区如下：
A: (0, 2) (3, 7)
B: (1, 4) (5, 6)
作为一个看起来像这样的图片：
-- ----
--- -
但是寻找最早停止时间规则会产生以下颜色：
A: (0, 2) (5, 6)
B: (1, 4)
C: (3, 7)
这是哪个分区：
-- -
---
----
所以这个贪心规则在这个例子中并不是最优的。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
