algorithm - 贪心算法的最优算法 : Interval Scheduling - Scheduling All Intervals

Question

我最近在 Tardos 和 Kleinberg 的算法设计的第 4 章中阅读了有关间隔调度算法的内容。为间隔调度问题提供的解决方案是这样的:

Sort the n intervals based on their finishing time and store in array F
A = [] #list of intervals
S = array with property that S[i] contains the finishing time of the ith interval
i = 0
For j = 0 to n-1
    if S[j] >= F[i] #this interval does not overlap with the ith interval
        i = j
        A.add(j)

C++/Java/Python 中的算法可以在这里找到:http://www.geeksforgeeks.org/greedy-algorithms-set-1-activity-selection-problem/

问题的扩展，也称为区间着色问题，可以解释如下。

We are given a set of intervals, and we want to colour all intervals so that intervals given the same colour do not intersect and the goal is to try to minimize the number of colours used.

书中提出的算法是这样的:

Sort the intervals by their start times in a list I
n = len(I)
For j = 1 to n:
   For each interval I[i] that precedes I[j] and overlaps it:
       Exclude the label of I[i] from consideration for I[j]
The jth interval is assigned a nonexcluded label

但是这个算法的运行时间不是O(n^2)吗？我想到了一个更好的，但我不确定它是否正确。基本上，我们修改了间隔调度的算法。

Sort the n intervals based on their finishing time and store in array F
A = []
x = 1
S = array with property that S[i] contains the finishing time of the ith interval
i = 0
while F is not empty:
    new = []
    For j = 0 to n-1
        if S[j] >= F[i] #this interval does not overlap with the ith interval
            i = j
            A.add(F[j])
        else:
            new.add(F[j])
    F = new
    Recompute S
    print x, A
    A = []
    x++

我的伪代码中可能有一个愚蠢的错误，但我希望你能理解我的算法试图做什么。基本上，我通过重复运行标准间隔调度算法来去除所有可能的着色。

那么，我的算法不应该打印区间的所有各种颜色吗？如果它是正确的算法，这是否比以前的算法更有效？如果不是，能否请您提供一个反例？谢谢!(更多关于间隔调度的信息:https://en.wikipedia.org/wiki/Interval_scheduling)

Answer 1

您的算法可能会产生次优解决方案。以下是您的算法将生成的示例:

---      -----
  ----
    ------------

很明显，对于相同的输入，以下 2 色解决方案(将由经过验证的最优算法生成)是可能的:

--- ------------
  ----   -----

最后，尽管本书提出的算法的伪代码描述确实看起来确实需要 O(n^2) 时间，但可以使用其他数据结构加快速度。这是一个 O(n log n) 算法:不是遍历所有 n 个间隔，而是按递增顺序遍历所有 2n 个间隔端点。维护一个按颜色排序的可用颜色堆(优先级队列)，最初包含 n 种颜色；每次我们看到一个区间起点，从堆中提取最小的颜色并将其分配给这个区间；每次我们看到间隔终点时，将其分配的颜色重新插入堆中。处理的每个端点(开始或结束)都是 O(log n) 时间，并且有 2n 个。这与对间隔进行排序的时间复杂度相匹配，因此整体时间复杂度也是 O(n log n)。