skip to content

When a conflict graph's slot count keeps climbing, how do you decide between better colouring and changing the model?

level: principalimportance: nice to knowfreq 26%

answer

  1. measure before optimising
  2. floor from mutual conflicts
  3. ceiling from the current colouring
  4. defensive edges cost real slots
  5. duplicate the resource to delete edges

basics

~20 s

Measure the floor first: the largest mutually conflicting group is a count no colouring can beat. If that floor is what is rising, only deleting conflicts or adding capacity helps; a wide gap above the floor means better colouring is still available.

solid answer

~40 s

Turn the argument into two numbers before spending anyone's time. The **floor** is the largest group of jobs that all clash — a certificate that no assignment goes lower. The **ceiling** is what your current colouring achieves. If the ceiling sits far above the floor, colouring effort is still worth something. If they are equal, colouring is finished by proof, and the only remaining levers change the graph: duplicate the contended resource so its edges disappear, split a job so it stops clashing with a whole family, or delete edges that encode *should not* rather than *cannot*. If the floor itself is what keeps rising, the work genuinely got more contended and capacity is the honest answer. Publishing both numbers is what stops a team chasing an impossible target.

go deeper

for a junior

Take away the habit: before asking how to schedule better, ask how few slots are even possible for this set of conflicts.

for a middle

Be able to produce both numbers — a mutually conflicting group for the floor, your assignment for the ceiling — and say what the gap between them means.

for a senior

Drive the diagnosis: identify whether the count rose because the model gained edges or because the assignment got worse, and act on the right one.

for a principal

Own the trade-off. Price bounded optimisation against recurring capacity, decide who may declare a conflict, and treat forcing the contention into a structured shape as the durable fix.

## Get two numbers before you get an opinion The chromatic number is a minimum over all assignments, so nobody in the room knows it. What you can obtain cheaply are bounds on either side, and the decision follows from where they sit: - **Floor** — exhibit a set of jobs that pairwise conflict. Its size is a lower bound anyone can verify by inspection. Where the conflicts come from intervals on a line, the busiest instant gives the floor directly and it is exact. - **Ceiling** — the slot count your current assignment achieves. The busiest job's degree plus one is a crude second ceiling that needs no run at all. Everything below is read off the relationship between those two. ## Three situations, three different answers 1. **Ceiling far above floor.** The assignment is the suspect. Try other orderings, or seed from a known-good grouping. This is bounded work with a known payoff — at best you recover the gap, never more. 2. **Ceiling equals floor.** Colouring is over, with a proof. Any further scheduling effort returns exactly zero, and continuing is the most expensive failure mode here because it is invisible: the team keeps producing valid schedules that cannot improve. 3. **The floor itself is climbing release after release.** The work genuinely became more contended. No algorithm answers this; the graph has to change or capacity has to grow. ## Levers that change the graph - **Duplicate the contended resource.** If jobs clash only because they share one exclusive thing, a second copy removes a whole block of edges at once and can cut the floor roughly in half. - **Split a hub job.** A job that clashes with everything sits in every mutual-conflict group and adds one to the floor by itself. Decomposing it into parts that contend with less is often the cheapest structural win available. - **Audit the edges.** Conflicts drawn defensively — "these two probably should not run together" — are indistinguishable from real ones once they are in the graph, and each can only push the count up. Ask for the failure mode each edge prevents; the ones with no answer are free slots. - **Relax the granularity.** Conflicts often exist only because jobs were cut at an arbitrary boundary. Merging two jobs that always run together deletes their conflicts with each other and can simplify the rest. - **Force a structured shape.** If the contention can be expressed as intervals on a timeline, or as two families that never clash internally, the count becomes both computable and provably tight, and the scheduling debate ends permanently. That is the highest-value change available, and it is a design decision, not an optimisation. ## Weighing the levers against capacity Capacity — one more slot, one more machine, one more window — is a recurring cost that is easy to price. Optimisation effort is a recurring cost that is hard to price and bounded above by the gap between the two numbers. Three consequences are worth stating in a review: - When the gap is one or two slots, adding capacity usually wins on cost even if optimisation would work, because the engineering is never finished — every new job perturbs the graph and reopens the question. - When the gap is large and the graph is stable, optimisation is worth funding once, then freezing behind a regression check on the slot count. - When the floor equals the capacity, the conversation stops being about scheduling at all and becomes a question about the product: which conflicts are we willing to stop enforcing? ## Making the decision durable Publish the floor next to the achieved count and keep both in the schedule's output. It changes the team's language from "the scheduler is slow" to "the model demands nine and we use nine", it makes an added conflict edge visibly expensive at the moment someone adds it, and it gives the next engineer a reason not to re-run an optimisation that was proved finished. The mathematics here is elementary; the leadership content is refusing to let an unbounded optimisation continue past the point where a two-line certificate shows it cannot pay.

  • What is the cheapest structural change when one job conflicts with everything?
    Split it. A job adjacent to every other sits inside every mutually conflicting group and adds exactly one to the floor on its own, so decomposing it into parts that contend with smaller sets removes its edges wholesale. Duplicating whatever resource it monopolises has the same effect from the other direction.
  • Why is adding one more slot sometimes strictly better than optimising the colouring?
    Because the payoff of optimisation is capped by the gap between your count and the proven floor, while its cost recurs every time the job set changes. If the gap is one slot, capacity buys the same outcome once. And if the count already equals the floor, optimisation cannot pay at all.
  • How do you stop a conflict model from inflating on its own?
    Make each edge justify a failure mode, and report the slot floor alongside the schedule so adding a conflict has a visible price. Defensive edges are indistinguishable from real ones once recorded, and because adding an edge can only hold the count steady or raise it, the drift is one-directional.

saying these in an interview costs you the question

  • Debates scheduling algorithms without measuring any lower bound
  • Keeps optimising a schedule already sitting at the proven floor
  • Treats every conflict edge as given rather than as a claim to justify
  • Believes more slots always indicate a worse scheduling algorithm
  • Assumes a structural change to the graph cannot lower the minimum