Greedy algorithm: Interval coloring

AlwaysNull picture AlwaysNull · Feb 16, 2016 · Viewed 7.4k times · Source

In interval scheduling, the algorithm is to pick the earliest finish time. But in interval colouring the former does not work. Is there an example or explanation on why picking earliest finish time won't work for interval colouring?

The interval colouring problem is: 
given
 a 
set 
of 
intervals,
 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. This can be thought of as the interval partitioning problem (if it makes more sense)

The interval scheduling problem that i'm referring to is: If you go to a theme park and there are many shows, the start and finish time of each show is an interval, and you are the resource. You want to attend as many shows as possible.

Answer

btilly picture btilly · Feb 16, 2016

This is just a case of playing around with pictures until you find an example. The first picture I drew that showed the problem had the following partitioning:

A: (0, 2) (3, 7)
B: (1, 4) (5, 6)

As a picture that looks like this:

-- ----
 --- -

But looking for the earliest stop time rule produces the following coloring:

A: (0, 2) (5, 6)
B: (1, 4)
C: (3, 7)

Which is this partitioning:

--   -
 ---
   ----

So this greedy rule fails to be optimal on this example.