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