Greedy Algorithm or using sets?

Question

i have been trying to figure out the answer to a question. And the question is as follows:

Given a list of time-periods, we have to find out if we can sort the work between two people, such that one person is not allowed to work for two overlapping time periods. For instance, let's say I have person A and person B. The format of the time periods #some_Number is the number of hours after midnight:

And the time periods are as follows:

360 480

420 540

600 660

Here, Person A can do job1, person B can do job 2, and person B/C can do job 3. Notice the same person could not do both job 1 and 2 as they overlap.

Now look at the example below:

0 1440

1 3

2 4

Here, it is impossible to delegate the work such that there is no overlap for anyone. All three time-periods overlap.

Now look at the example below:

99 150

1 100

100 301

2 5

150 250

Here, the jobs can be delegated as ABBAA.

Can someone help me with a way to do this?

All i can think of is a brute force algorithm/or implement it using sets.

Answer 1

You are seeking the minimum number of colours (people) needed to colour (work on) the interval graph defined by the given time periods. The graph colouring problem on interval graphs is solvable in polynomial time by a greedy algorithm:

• Sort time periods by starting time
• Go through the periods in order and assign the next period to the person whose current last job ends earliest and can work on this job; if there is none, allocate a new person