Optimal algorithm for the Greedy Algorithm: Interval Scheduling - Scheduling All Intervals

Question

I recently read about the Interval Scheduling algorithm in chapter 4 of Algorithm Design by Tardos and Kleinberg. The solution provided to the Interval Scheduling Problem was this:

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)

This algorithm in C++/Java/Python can be found here: http://www.geeksforgeeks.org/greedy-algorithms-set-1-activity-selection-problem/

An extension of the problem, also known as the Interval Coloring Problem, can be explained as follows.

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.

The algorithm proposed in the book was this:

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

However isn't this algorithm's running time O(n^2)? I thought of a better one, but I'm not sure if it is correct. Basically, we modify the algorithm for Interval Scheduling.

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++

I might have a silly bug in the pseudocode but I hope you understand what my algorithm is trying to do. Basically I'm peeling off all possible colourings by repeatedly running the standard interval scheduling algorithm.

So, shouldn't my algorithm print all the various colourings of the intervals? Is this more efficient than the previous algorithm, if it is a correct algorithm? If it is not, could you please provide a counter-example? Thanks! (More about interval scheduling here: https://en.wikipedia.org/wiki/Interval_scheduling)

j_random_hacker j_random_hacker · Accepted Answer · 2016-11-15T16:53:13

Your algorithm can produce a suboptimal solution. Here's an example of what your algorithm will produce:

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

Clearly the following 2-colour solution (which will be produced by the proven-optimal algorithm) is possible for the same input:

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

Finally, although the pseudocode description of the book's proposed algorithm does indeed look like it needs O(n^2) time, it can be sped up using other data structures. Here's an O(n log n) algorithm: Instead of looping through all n intervals, loop through all 2n interval endpoints in increasing order. Maintain a heap (priority queue) of available colours ordered by colour, which initially contains n colours; every time we see an interval start point, extract the smallest colour from the heap and assign it to this interval; every time we see an interval end point, reinsert its assigned colour into the heap. Each endpoint (start or end) processed is O(log n) time, and there are 2n of them. This matches the time complexity for sorting the intervals, so the overall time complexity is also O(n log n).

Optimal algorithm for the Greedy Algorithm: Interval Scheduling - Scheduling All Intervals

1 Answers