Interval Assignation Problem

Revision en2, by mavd09, 2019-12-04 06:06:28

Hi Codeforces!

I'm dealing with a problem, given N workers, each one with time intervals in which they can work and 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.

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)