Interval Assignation Problem
Difference between en3 and en4, changed 24 character(s)
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!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English mavd09 2019-12-04 17:24:43 16 Tiny change: ' worker W_i is going ' -> ' worker W_ is going '
en4 English mavd09 2019-12-04 17:16:00 24
en3 English mavd09 2019-12-04 17:13:57 945
en2 English mavd09 2019-12-04 06:06:28 3 Tiny change: 'trictions were met. Al' -> 'trictions are met. Al'
en1 English mavd09 2019-12-04 06:04:55 647 Initial revision (published)