The Overtime Scheduling Bug
A hospital's shift-scheduling tool assigns nurses to 4-hour blocks. The team wrote a greedy routine: sort nurses by fewest assigned hours, then for each block assign the first nurse who is free and has not exceeded 36 hours this week. In testing with 12 nurses and 60 blocks it always produced a valid schedule in under 40 ms. After adding a new constraint -- no nurse may work two consecutive blocks on the same day -- the routine sometimes returns a schedule with an unfilled block, even though a valid complete schedule exists. A manager reports the tool 'randomly' fails, and the failure rate rises as more nurses request part-time hours. The team proposes adding a retry loop with a shuffled nurse order and a 2-second timeout.
1. Explain why the failures are not random and why the retry loop is unlikely to fix the underlying problem. Recommend an algorithmic change.
Read the worked answer
The failures are deterministic, not random. A greedy algorithm makes an irrevocable choice at each block: it picks the first eligible nurse by current hours. That choice can consume a nurse whose only remaining availability matches a later, more constrained block. The new consecutive-block rule makes some blocks much harder to fill, so the greedy order matters far more than before. Part-time requests shrink each nurse's feasible set, which increases the chance that an early greedy pick blocks a later one -- hence the rising failure rate. That is a structural property of greedy choice under constraints, not a flaky bug.
A shuffled-retry loop is a randomized search: it explores different greedy orderings but never revisits or backtracks a partial assignment. It may help on easy instances and will look like it 'sometimes works', but it gives no guarantee and its 2-second timeout silently returns an incomplete schedule. It also makes failures nondeterministic and harder to debug.
Better options, in order of effort:
- Model it as a constraint-satisfaction or assignment problem and use backtracking with constraint propagation (assign most-constrained blocks first, prune when a nurse's remaining feasible blocks are exhausted). This is exact and small enough at 12 nurses / 60 blocks.
- Or formulate as bipartite matching / flow if each block needs exactly one nurse and constraints can be encoded as capacities.
- Keep a deterministic fallback and report infeasibility explicitly rather than timing out.
Also add a regression test with the failing part-time-heavy instance so the fix is verifiable.
2. The team wants to prove the new scheduler never returns an incomplete schedule when one exists. What would you tell them to test and what can and cannot be proven this way?
Read the worked answer
Testing can raise confidence but cannot prove correctness for all inputs. What they should test:
- Exhaustive small cases: enumerate all instances with, say, up to 6 nurses and 12 blocks, including edge cases (zero part-time nurses, all nurses part-time, blocks that no nurse can fill). Compare the solver's output against brute-force feasibility. This is the strongest evidence available and is tractable at that size.
- Adversarial instances: tight capacity (total available hours just equal to required hours), long consecutive-run constraints, and nurses with identical availability.
- Infeasible instances: confirm the solver reports infeasible rather than hanging or returning partial output.
- Property checks: any returned schedule satisfies every constraint; no block is double-assigned; hours caps respected.
What cannot be shown by testing: that no larger or unusual instance fails. Exhaustive testing over all inputs is infeasible beyond tiny sizes. If they need a guarantee, the argument must be a correctness argument about the algorithm -- for backtracking with propagation, that pruning only removes provably infeasible partial assignments, and that the search is complete. That reasoning, plus exhaustive small-case testing, is a reasonable standard. A timeout-based 'give up' path must be documented as best-effort, not guaranteed.