Dunder Mifflin is a famous paper company. Unfortunately, due to the incompetence of one of its branch managers, Dunder Mifflin is under fire. You see, recently, a disgruntled employee printed papers on which curse words were written. The quabbity assuance manager is an old guy named Creed, who totally forgot about his duties, and now, the customer care employee Kelly Kapoor is under heavy load. Customers have scheduled calls to complain to her about the paper situation, but the call schedules overlap. Now, the branch manager, Michael Scott, has decided that all the other employees need to help Kelly.
The thing is, no one really wants to miss their own sales calls to help Kelly, and there's only so many people Michael can pursuade to help her. As such, we need to find out the maximum number of extra employees Michael needs to convince to help with the customer care calls.
There are some customers, who have called ahead in the day to schedule a call with Kelly. The call schedule looks like this:
Mr. Rogers: 10 AM to 11 AM
Mr. Tim: 10:30 AM to 1 PM
Ms. Jan: 10:40 AM to 1 PM
Mr. Hunter: 2 PM to 3 PM
If we look closely, we can see that the timing schedules can be put in a number line as such:
From the image above, it is quite evident, that the total number of employees that Michael needs to convince is equal to 3, since at any given time, there are at most 3 conversations going on!
Let's construct a simple solution to this problem. Let's take a single employee at a time. If another call comes in, and the employee is free, then s/he will answer the new call. Otherwise, Michael will need to convince another employee to wo/man the call. Simple as that, right?
1. Start
2. Customer care employee list = [Kelly]
3. Sort the calls in order of their starting times
4. While calls are not finished:
a. Accept a call
b. if any employee in Customer care employee list is free:
i. Assign the call to free employee
otherwise,
i. Convince a new employee to wo/man the phone
ii. Add the new employee to the Customer care employee list
5. End
This is a solution to our problem. You can see that for each call, it tries to find a empty employee and assign the call immediately. What you just read was an algorithm that falls under the class of "greedy" algorithms, that try to find optimal solutions based on the current best outcome. The given algorithm seems sound, but we are yet to prove its correctness. Let's first take a look at its bounds.
Output Bounds
While looking at any algorithm, we shoult try to ascertain its input/output bounds. To analyze the required output bounds, let's take some extreme-case scenarios into consideration first:
The first scenario might never occur, so let's assume that there's at least one caller in the queue. Taking that assumption, the maximum number of employees required will be $0 < e \leq n$, where $n$ is the number of callers, and $e$ denotes the number of employees required
Termination
Every algorithm is required to be checked for termination. We can see that even if every caller calls at the same time, equal number of employees can pick the calls. If the call lengths are not indefinite, then every call is bound to be complete and every employee becomes free in the end. So this algorithm will terminate. (Proof left to the reader. Can we use pigeonhole principle here?)
Time Bound
The next thing that we're going to do is check the algorithm for its timing bounds. There are some steps in this algorithm, for which the timing bounds are different.
Finally, Proof of Correctness
We have proved that the outputs for the algorithm are bounded, and it indeed, terminates for the given input. Now we have to prove that the greedy solution that we have proposed is true. Proving correctness of greedy algorithms can be tricky.
Let us assume that our algorithm outputs $e$ employees as the required count. The $e$-th employee was persuaded, because all $e-1$ employees were busy with their own calls. So this must mean that for the current call to be allocated to a new employee, the call must've started later than some $x$ calls before it and those calls will end sometime later than the current call. Thus, we have $e$ calls overlapping at the current time, which denotes the depth in our previous image. So this means that for any instance of time, the maximum depth required was $e$, as employees can be freed after calls but remain in the free queue. So our queue of employees will increase to a maximum size of $e$.
To implement this algorithm, let's first arrange the scheduled calls in order of their starting. The calls are arranged in order of their beginning time into a list $calls$. Then, we initialize an empty pool of workers. For each $call$ in $calls$, we check the pool to see if there are any free workers. If there are free workers, we will assign the $call$ to them, else we will add a new $worker$. The implementation in python is fairly simple for this task.
def sortJobs(jobList):
# assume job list looks like [{"start": 10, "end": 10.75}, {"start": 10.5, "end": 1}, ...]
return jobList.sort(key = lambda x: x['start'])
def maxEmployeesRequired(jobList):
sortedJobList = sortJobs(jobList)
customerCare = []
for call in sortedJobList:
assigned = False
for employee in customerCare:
if employee['end'] <= call['start']: # This employee is free!
assigned = True
employee['end'] = call['end']
break
if not assigned:
newEmployee = {"end": call['end']}
customerCare.append(newEmployee)
return len(customerCare)
Note: In this implementation I have used a linear search which increases the bounds to $O(n^2)$. To implement the search, we can use a priority queue, which I have explained in this tutorial.
This algorithm can be seen widely in usage, while deciding the number of classrooms required to conduct classes. The scheduled calls are scheduled lectures, and the number of employees denotes the number of classrooms required.
At the end of the day, Dunder Mifflin is saved!
