PROBLEM LINK:
Author: Maksym Bevza
Tester: Istvan Nagy
Editorialist: Miguel Oliveira
DIFFICULTY:
Medium
PREREQUISITES:
Graph Theory, Minimum Cut, Maximum Flow
PROBLEM:
Consider that there are D business days, each with N working hours. The availability of each of the P employees is given for each hour of the business days. The employees also need to have at least 1 hour for lunch in a given time interval.
Given a call center schedule constraints, find if it’s possible to make a schedule for all employees so that there are always a given number of employees available to talk with clients, satisfying the constraints.
EXPLANATION:
Subtask1
N, H, D and P are really small. We can brute force to see if there is a feasible solution.
Subtask 2
Same as subtask 3 but with an inefficient implementation.
Subtask 3
The problem involves deciding, for each person, what activity they will do in each hour of the day, satisfying some restrictions. This resembles an assignment problem. In fact, we can use a similar approach to assignment problems based on network flow.
We can model this problem as a graph where the vertices represent people, person i talking to clients or having lunch, and the edges contain the given constraints.
A constraint of the form ‘person x must not talk to clients more than L_x hours per week’ can be modelled as an edge with capacity L_x.
Now the tricky part is the lunch time.
There are N hours in each day and we must guarantee there is a free hour during lunch time. To do this, we create 2 nodes per person and per day: “lunch hours at day d” and “normal hours at day d”.
Suppose \Delta_{LT} = {LT}_{end} - {LT}_{begin} - meetings, the number of lunch hours not filled with meetings. Then, we have N - \Delta_{LT} - meetings normal hours and \Delta_{LT} free lunch hours. In order to have a free lunch hour, \Delta_{LT} must be positive. One of these must not be filled with meetings nor clients, so the actual capacity associated with lunch hours is \Delta_{LT} - 1. This way, we ensure that at least 1 of these hours is not assigned work.
Now, we create nodes for each pair (day, hour) and connect these with the nodes associated with each <person, normal/lunch hours> if the person does not have meeting during that hour in that day: F_{k, i, j} = 1.
Finally, we connect the (day, hour) nodes with a sink vertex with capacity equal to R_{i, j}.
Suppose we have 5 days: monday - friday, with H = 5 and lunch hours at hours 3 and 4. A possible resulting graph is the following
If the minimum cut between vertices S and T equals \sum_{R_{i, j}} then we can satisfy all customer requirements.
The minimum cut can be calculated using an efficient maximum flow algorithm such as Dinic’s algorithm.