PROBLEM LINK:Author: Maksym Bevza 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:Subtask1N, H, D and P are really small. We can brute force to see if there is a feasible solution. Subtask 2Same as subtask 3 but with an inefficient implementation. Subtask 3The 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. Sample Solutions
This question is marked "community wiki".
asked 16 Feb '16, 00:18

Please someone tell whether greedy solution would be correct for this problem or not as I got an AC using greedy technique in O(n^3) complexity. AC Solution . answered 16 Feb '16, 04:53
Can you describe the idea of your greedy algorithm ? Its painful to look at some code and derive the idea out of it.
(17 Feb '16, 22:48)
