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!
↵
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!
