A scheduler pairs work items to eligible engineers until no further pair fits, so why can the result still be undersized?
answer
- two adjectives, not synonyms
- cannot extend versus cannot beat
- one early pair blocks two
- local check versus global claim
- never below half the best
basics
~20 sA maximal pairing is one no extra pair can be added to; a maximum pairing is one of the largest possible size. Stopping when nothing more fits guarantees only the first, because an early pair can block two later ones.
solid answer
~40 sThe two words are not synonyms. A **matching** is a set of item-engineer pairs in which no item and no engineer appears twice. It is **maximal** when no eligible pair can be added to it, and **maximum** when no matching on that eligibility graph has more pairs. Adding pairs one at a time always ends at a maximal matching, and that can be strictly smaller than the maximum: if item `A` is eligible for engineers `X` and `Y`, and item `B` only for `X`, then taking `A-X` first is maximal at size one, while `A-Y` plus `B-X` staffs both items. The consolation is a bound rather than an equality: a maximal matching is never smaller than half a maximum one, because each of its pairs can block at most two pairs of the optimum.
go deeper
Recall that an assignment can leave items unstaffed, and that "no more pairs fit" is a different claim from "no better assignment exists". Know the words matching, maximal and maximum.
Explain the difference in one breath - maximal means non-extendable, maximum means largest - and produce a three-edge example on the spot where an early pair strands an item that had only one eligible engineer.
Judge when merely maximal is acceptable. It is within a factor of two of optimal and is cheap, which suits a sweep that reruns constantly, but not a plan a team commits to for a sprint.
Decide what the assignment service promises. Guaranteeing a maximum assignment costs more work per run but makes the reported size independent of input order; guaranteeing only maximality makes that number wobble between runs, which is a reporting problem before it is a math problem.
## Three words, three different claims Start from the object. Model staffing as a **bipartite graph**: one side is the backlog items, the other side is the engineers, and an edge joins an item to an engineer who is eligible to take it. A **matching** `M` is a set of edges no two of which touch the same vertex - each item gets at most one engineer, each engineer at most one item. Everything below is a property *of a matching*, not of the graph. | Term | Exact claim | How you would check it | |---|---|---| | Matching | No item and no engineer is used twice | Scan the chosen pairs for a repeated endpoint | | Maximal matching | No further eligible pair can be added to it | Every remaining edge has at least one endpoint already used | | Maximum matching | No matching on this graph has more pairs | Requires an argument about the whole graph, not just this set | | Perfect matching | Every vertex on both sides is paired | Only possible when the two sides have equal size | The trap is that **maximal** is a local, checkable property, while **maximum** is a global one. You can verify maximality by looking only at the edges you did not take. You cannot verify maximality and conclude optimality. ## The smallest example where the difference bites Two items and two engineers: - item `A` is eligible for engineers `X` and `Y`; - item `B` is eligible only for engineer `X`. Pair `A` with `X` first. Now `B` has one eligibility, `X`, and `X` is taken - no pair can be added. That matching has size **1** and is genuinely maximal. But `A-Y` together with `B-X` is a matching of size **2**, so the maximum is 2. Nothing was wrong with the pairing rule; the order of decisions consumed the only engineer that item `B` could ever use. This is the whole phenomenon, and it does not get milder at scale. It gets worse: an engineer with broad eligibility is exactly the one a naive sweep grabs first, and exactly the one a narrowly-eligible item depends on. ## Greedy is not worthless - the factor-of-two bound Maximality does buy something provable. Let `M` be any maximal matching and `M*` a maximum one. Take any pair `e` in `M*`. It cannot be disjoint from every pair of `M`, because then `e` could have been added to `M`, contradicting maximality. So every pair of `M*` shares an endpoint with some pair of `M`. Each pair of `M` has only two endpoints, so it can absorb at most two pairs of `M*`. Therefore: 1. `|M*| <= 2 * |M|`, so `|M| >= |M*| / 2`; 2. the bound is tight - the three-edge example above achieves exactly 1 against 2; 3. the bound holds for *any* maximal matching, so it needs no assumption about how the pairs were chosen. Half of optimal is a real guarantee, and for a background sweep that will run again in ten minutes it is often enough. For a plan a team commits to for a sprint, it is not: the missing half is a person's week. ## Perfect is a stronger word again A **perfect matching** leaves no vertex unpaired on either side. Two consequences follow immediately and are worth saying out loud: - every perfect matching is maximum, because nothing larger can exist once every vertex is used; - a maximum matching need not be perfect - in the example above, the maximum matching of size 2 is perfect only because the sides happen to have two vertices each. When the two sides differ in size, a perfect matching is impossible outright, and the honest question becomes whether every vertex of the *smaller* side can be paired - that is the saturation question, answered by a condition on the eligibility lists rather than by counting. ## What to do with the distinction at work The practical discipline is to stop treating "the scheduler could not add anything else" as an answer. Three habits follow: 1. **Report the size, and say which claim it supports.** "14 items assigned, and no more pairs fit" is a maximality claim. "14 items assigned, and no assignment does better" is a much stronger claim that needs a separate justification. 2. **Expect order sensitivity.** If a merely maximal assignment is acceptable, accept also that re-running with items in a different order can change the count. If that instability is unacceptable to the people reading the output, you needed the maximum. 3. **Separate the size from the plan.** The number is what you defend in a review; the specific set of pairs is what the team executes. Two different maximum matchings are equally optimal and may be very different plans, so tie-breaking on fairness or preference is a design decision, not a mathematical one.
- Can a maximal pairing ever be less than half the size of a maximum one?No. Every pair of the maximum matching must share an endpoint with some pair of the maximal one, otherwise it could have been added and the matching was not maximal. Each maximal pair has two endpoints, so it blocks at most two optimal pairs, which gives at least half. The three-edge example, one against two, shows the bound is tight.
- What extra property makes a pairing perfect rather than merely maximum?A perfect matching leaves no vertex unpaired at all, so every item has an engineer and every engineer has an item, which forces the two sides to have equal size. Every perfect matching is maximum, but a maximum matching need not be perfect, and when the total number of vertices is odd no perfect matching can exist.
Filling a car park by letting each arriving car take the first space that fits leaves a lot where nothing more can be parked, yet a different arrangement would have held more cars.
saying these in an interview costs you the question
- Uses maximal and maximum as interchangeable words
- Claims a pair-by-pair sweep always reaches the largest assignment
- Says adding one safe-looking pair can never cost you later
- Calls any assignment that uses every engineer a perfect matching
- Assumes improving an assignment means discarding it and starting over