Hi Codeforces!

I am dealing with the following problem:

Given N workers, each one has one or more time intervals that represent the time it will be available to work.

Also, I have M tasks, each one represented as an interval [from, to].

The problem is to assign all the tasks to the workers.

Each worker can only work in one task at the same time and each task must be executed just for one worker in the given interval, i.e. if the worker W_i is going to work in the task T_j, it must be available to work in the interval of this task.

It is guaranteed that a solution exists.

Assume that N and M are less than 100 and the intervals are between 0 and 20000.

One example, we have 2 workers:

The first worker will be available to work in the following intervals:

1. [15, 37]

The second worker will be available to work in the following intervals:

1. [30, 45]
2. [55, 65]

And we have the following tasks:

1. [20, 30]
2. [55, 61]
3. [31, 37]

So, one possible assignation could be:

• [20, 30] -> Assigned to the first worker
• [56, 61] -> Assigned to the second worker
• [31, 37] -> Assigned to the first worker

Another solution could be:

• [20, 30] -> Assigned to the first worker
• [56, 61] -> Assigned to the second worker
• [31, 37] -> Assigned to the second worker

I have a greedy approach, but not sure if it always works. I will be grateful if anyone can help me with any approach, idea or paper.

Thanks!