In an earlier post I mentioned that I enjoy reframing classic algorithms questions as real-world problems to motivate student interest. One problem I’ve used as an exercise in recursive backtracking (both on an exam and in a recent assignment) is a version of the bin packing problem framed in terms of scheduling patients in a hospital. The problem is described like this:
You are working at a hospital trying to coordinate times in which non-emergency patients can meet with their doctors. Each doctor has a maximum number of hours each day that she can see patients. For each patient, you are given how much time she will need to spend with her doctor. Given the amount of time that each doctor is free on a given day, along with the amount of time required for each patient, you are interested in determining whether or not it is possible for every patient to be seen.
I guess that since the doctors have a bunch of patients to see and no fixed plan to see them, they’re Doctors Without Orders!
This problem is essentially the bin packing problem with the modification that each bin might have a different total size. Each doctor forms a bin whose capacity is equal to the number of free hours in the doctor’s schedule, and each patient is an object to place into a bin whose size is equal to the number of hours for which she needs to be seen.
The theming on this problem is quite nice – there’s a clear motivation behind why you might want to find the most efficient way to schedule patients across doctors. Since it’s NP-hard, most greedy solutions will fail to give optimal solutions in some cases (which is a great way to introduce students to some concepts from algorithms design). It also generalizes in a lot of fun ways. Imagine you have a bunch of doctors like these and want to plan a full week’s schedule, or otherwise try to get everyone seen as fast as possible. How would you do that? How might you define a measure of “fairness” in terms of workload across the doctors, then try to maximize fairness while getting everyone seen? What if the doctors are specialists in different subfields and each patient needs to be seen by a doctor with a certain set of skills? And on top of it all, the problem has a really nice recursive backtracking solution: fix an unassigned patient, and for each doctor with time available to see them, try assigning the patient to that doctor.