Alw*_*ull 4 algorithm greedy graph-coloring
在间隔调度中，算法是选择最早的完成时间。但是在间隔着色中，前者无效。是否有示例或解释说明为什么最早的完成时间不能用于间隔着色？
间隔着色问题是：给定？一组“间隔”，我们要“给所有颜色上色”吗？间隔？这样？间隔？给吗？该？相同？颜色？不相交？和“目标”？是“尝试”为？最小化使用的颜色数。可以将其视为间隔分区问题（如果更合理）
我指的是间隔安排问题：如果您去主题公园并且有很多演出，那么每个节目的开始和结束时间就是一个间隔，您就是资源。您想参加尽可能多的演出。
在找到示例之前，这只是玩转图片的一种情况。我绘制的第一张显示该问题的图片具有以下分区：
A: (0, 2) (3, 7)
B: (1, 4) (5, 6)
如图所示：
-- ----
--- -
但是寻找最早的停止时间规则会产生以下颜色：
A: (0, 2) (5, 6)
B: (1, 4)
C: (3, 7)
这是哪个分区：
-- -
---
----
因此，此贪婪规则在此示例中并非最佳。
如果您只需要一个关于着色的贪婪算法的反例，@btilly 已经提供了一个。
我试图给出理由以使其更加直观。
首先，对于调度问题，确实可以证明贪心算法是有效的。这个想法是这样的：
如果我不选择结束时间最早的节目，我就无法获得更好的结果，让我们看看。
如果有两个区间 A、B，其中 A 的结束时间较早，则 B 是
然而，对于着色问题，则完全是另一类问题。
您被迫选择所有间隔，而问题的答案是所有时间中冲突间隔的最大数量。
试着这样想：一直以来，最多有 5 场考试同时进行，你至少需要使用 5 个教室（颜色），对吧？
所以我们无法通过选择最早完成时间来找到这一点，时间没有告诉你任何事情。
它可能会帮助您决定是否选择这个间隔（就像在调度问题中），但不能告诉您所需的最少资源数。它们只是不同类别的问题。
编辑：
重新阅读OP的问题后，据我所知，这里有更多关于着色问题的细节。
定义depth为始终最大冲突数。从逻辑上讲，我们知道depth是下界，但我们必须证明它也是上限（通过矛盾）。
证明
证明需要按开始时间升序或结束时间降序对间隔进行排序，如下所示：
假设depth区间集合的 是d，且答案大于d。令x为我们处理的第一个使用资源的区间d+1，由于处理顺序是按开始时间升序排序的，这意味着至少有d区间在 x 之前开始x且与 x 冲突，则该depth集合的 至少d+1，矛盾。所以d=depth也是答案的上界，是区间着色的最优答案。
请注意，如果您按开始时间降序排序或按结束时间升序排序，则不能使用相同的推理。
概念/目标
现在我们知道深度就是答案，我们必须找到它。从概念上讲，如果您发现使用开始时间或结束时间、升序或降序，所有选项都可以为您提供间隔集的深度，这并不重要。
实施考虑
然而，对于实现，如果你必须在 O(n lg n) 中找到它，你将不得不使用贪婪方法 + 一些数据结构，这可能需要间隔有某种排序。但这是另一回事了，它是为了实现，从概念上来说，没关系，你只想找到区间集的深度。
长话短说
对于区间调度问题，贪心法本身确实已经是最优策略；而对于区间着色问题，贪心法仅有助于证明深度就是答案，并且可以在实现中使用来找到深度（但不是像@btilly的反例中所示的方式）