Hi Codeforces!↵
↵
I' am dealing with athe following problem, g:↵
Given N workers, each onewithhas one or more time intervals in which they can work andthat 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 in such a way that worker's restrictions are met. Also, each worker can only work in one task at the same time. It is guaranteed that a solution exists.↵
↵
Assume that N and M are less than 100 and the intervals are between 0 and 20000.. ↵
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!↵
↵
↵
I
Given N workers, each one
Also, I have M tasks, each one represented as an interval [from, to]. ↵
The problem is to assign all the tasks to the workers
↵
Assume that N and M are less than 100 and the intervals are between 0 and 20000.
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!
↵
