Matching schedules between users and providers I have a problem I've been dealing for the past few days, and I'm pretty stuck.

Each user has a schedule for a given week, such as Mondays 9:00-12:00 and 14:00-18:00, Tuesdays... and so on. Each provider has another schedule for himself.

The problem is: Get the best k (different) solutions such that each solution assigns the minimum amount of providers to cover the entire schedule from the user? Where a solution is a set of pairs (Provider, schedule he will cover) and two solutions are considered equal if they contain the same providers (and different if they are not equal).

Also, take into account that any day could be split in sub-intervals and assigned to different providers. An example for a solution for the schedule shown before could be: {(Provider1, Monday 9:00-12:00), (Provider1, Monday 14:00-16:00), (Provider1, Monday 16:00-18:00)}

I've been looking into the Interval Partitioning Problem, Bipartite Matching Problem, and Assignment Problem, and none of them seem to adjust to my case.

Any ideas on how I could model this problem?
I think your problem is actually not a scheduling problem but a set cover problem. Just cut the time line in the atomic time parts of providers and assign them indices.

For instance, considring only one day for user from 8h to 14h:


provider 1: 7h-10h
provider 2: 6h-9h
provider 3: 10h-16h


The cut-off is:


6h-7h
7h-9h
9h-10h
10h-16h


and your problem is solving the minimum set cover of {2, 3, 4} with:


provider 1: {2, 3}
provider 2: {1, 2}
provider 3: {3, 4}


with evident solutions providers 1&amp;3 or 2&amp;3.

Nevertheless, this is a NP-problem and you likely have to test most of combinatoric if you really want to get optimal solutions. Sometimes this type of application contain some constraints or patterns that may help you to reduce the problem.