Every backlog item lists the engineers allowed to take it, so what condition on those lists decides whether all items can be staffed at once?
answer
- compare sets, not totals
- neighbourhood of every subset
- at least as many as the set size
- one violating set explains everything
- shortfall size caps the assignment
basics
~20 sAll items can be staffed at once exactly when every set of items is collectively eligible for at least as many distinct engineers as that set has items. That is Hall's condition, and a violating set is the proof of failure.
solid answer
~40 sCompare **sets**, not totals. For every subset `S` of items, let `N(S)` be the set of engineers eligible for at least one item in `S`. **Hall's marriage theorem** says a matching staffing every item exists if and only if `|N(S)| >= |S|` for all such `S`. One direction is obvious - `|S|` items need `|S|` distinct engineers drawn from `N(S)` - and the content of the theorem is that no other obstruction exists. So a single violating set is a complete explanation of failure: five items whose eligibility lists together name only three engineers cannot all be staffed, no matter how the assignment is arranged. Note the asymmetry: the condition saturates the item side. It gives a pairing covering both sides only when the two sides have equal size.
go deeper
Recall that having as many engineers as items does not mean every item can be staffed, because eligibility restricts who may take what.
State the condition in set form and explain the easy direction: a group of items needs at least that many distinct engineers among their combined eligibility lists.
Show you use the theorem as a certificate. When staffing fails, name the constrained set and the shortfall it forces, rather than reporting that the scheduler could not finish.
Frame eligibility breadth as a capacity risk the organisation owns. The binding constraint is usually a small specialist pool serving many items, and cross-training targets that set specifically rather than adding headcount anywhere.
## Totals are not the test The intuitive check - "we have 20 engineers and 20 items, so it should work out" - is wrong, and it is wrong in a way that costs real sprints. Eligibility is structure, not volume. Twenty engineers are useless to an item that names none of them. The correct object is the **neighbourhood**. For a set `S` of items, `N(S)` is the union of the eligibility lists of the items in `S` - every engineer who could take at least one of them. **Hall's condition** is: > for every subset `S` of the item side, `|N(S)| >= |S|`. **Hall's marriage theorem** states that this condition is both necessary and sufficient for a matching that pairs *every* item with an engineer. | Claim | Status | Why | |---|---|---| | Condition is necessary | Easy | `|S|` items need `|S|` distinct engineers, all drawn from `N(S)` | | Condition is sufficient | The theorem | No obstruction other than a shortfall on some set can exist | | Totals suffice (`#engineers >= #items`) | False | Nine items sharing three eligible engineers fails while totals look healthy | | Each item having one option suffices | False | It is the `|S| = 1` case only, the weakest instance of the condition | ## Reading the two directions correctly The necessary direction is a counting argument anyone can reconstruct: if a matching staffs all of `S`, the partners are distinct engineers and each lies in `N(S)`, so `N(S)` has at least `|S|` members. Contrapositive: any set whose neighbourhood is too small makes full staffing impossible. The sufficient direction is the surprising one and is what makes the theorem useful. It says the **only** way full staffing can fail is a set with too few eligible engineers. There is no subtler parity obstruction, no bad interaction between separate groups - find no deficient set and the assignment exists. Being an *if and only if* is why a violating set functions as a certificate. "We could not staff everything" is a report about an attempt. "Items `i3, i7, i9, i12, i15` are collectively eligible for only three engineers" is a proof, and it cannot be argued away by re-running with a different ordering. ## When the condition fails: the deficiency The theorem has a quantitative companion. Define the **deficiency** of a set `S` as `|S| - |N(S)|`, and let `d` be the largest deficiency over all subsets of items. Then the maximum number of items that can be staffed is exactly `|items| - max(0, d)`. A worked case: 20 items, of which 9 are eligible only for the same 3 engineers. That set has deficiency `9 - 3 = 6`, so at most `20 - 6 = 14` items can be staffed and at least 6 must go unassigned. Two wrong arithmetics to avoid: - `20 - 3 = 17` subtracts the engineer count instead of the deficiency; - `20 - 9 = 11` writes off the whole constrained set, although three of its nine items can be staffed. The deficiency turns a yes/no theorem into a number you can put in a capacity plan, and into a target: reduce the worst deficiency by one and the ceiling rises by one. ## Which side the condition saturates The condition as stated is about subsets of **items**, and what it delivers is a matching covering every item. It does not promise every engineer is busy. Three cases are worth separating: 1. **Fewer items than engineers.** Hall's condition on the item side gives full staffing of the items, with engineers left idle. There is no perfect matching, and none was needed. 2. **Equal sides.** Hall's condition on the item side gives a matching covering all items, and since the sides are the same size it covers every engineer too - a perfect matching. 3. **More items than engineers.** The condition fails immediately, taking `S` to be all items, and the deficiency measures how badly. A related caution: satisfying the condition on one side says nothing by itself about the other side when the sizes differ. If you need every engineer occupied, that is the symmetric question on the engineer side, and it needs its own check. ## Practical reading A few habits follow from taking the set form seriously: - treat **narrow eligibility lists as the risk**, not headcount - the dangerous configuration is many items sharing a small pool of specialists; - when full staffing fails, look for the **witnessing set** rather than for a scheduler bug, because that set is the actual finding; - remember the condition is a **characterisation, not a procedure**: it quantifies over exponentially many subsets and is not meant to be tested one subset at a time. Its role is to say what full staffing means and what failure proves.
- Does the condition have to be tested subset by subset in practice?No, and it is not meant to be - there are exponentially many subsets in the number of items. The theorem is a characterisation, not a test procedure: it tells you what full staffing is equivalent to, and it guarantees that when staffing fails a witnessing set exists. Producing such a witness is a job for the assignment machinery, not for enumeration.
- What does the deficiency form tell you when the condition is violated?The largest shortfall over all subsets, `max(|S| - |N(S)|)`, is exactly the number of items that must go unstaffed. So the maximum staffable count is the item count minus that shortfall. It converts a yes/no theorem into a ceiling you can quote, and into a concrete improvement target.
- If the condition holds for the items, does every engineer end up busy?Only when the two sides are the same size. With more engineers than items, the condition gives full staffing of the items while some engineers stay idle. Requiring every engineer to be busy is the symmetric question on the engineer side and needs its own check.
saying these in an interview costs you the question
- Checks only that each item has at least one eligible engineer
- Compares headcounts instead of comparing sets to their neighbourhoods
- Reads the condition as necessary but not sufficient
- Assumes the condition on one side yields a pairing covering both
- Proposes enumerating all subsets as the way to apply it