= Shortest-duration interval scheduling counterexample
In this separate three-job example, labels $A,B,C$ denote new jobs:
$$
A=[0,5),\qquad B=[5,10),\qquad C=[4,6).
$$
Their durations are five, five and two. Consider the rule "accept a shortest remaining job, discard all jobs conflicting with it, and repeat". It selects $C$ first. But $C$ overlaps $A$ on $[4,5)$ and $B$ on $[5,6)$, so both are discarded. The rule returns one job, while the compatible <subset> $\{A,B\}$ contains two. The common endpoint five is allowed, and no <feasible solution> contains all three jobs, so two is the <maximum>.
\Image[/interval-scheduling-shortest-duration-trap.png]
{title=A two-unit job blocks two compatible five-unit jobs}
{description=A separate three-job <counterexample> to choosing shortest duration. The left panel accepts only $C=[4,6)$; the right panel accepts $A=[0,5)$ and $B=[5,10)$. Shaded bands mark the two positive-length overlaps with $C$.}
Duration alone ignores where a job sits. Here the shortest job straddles the useful handover time. Earliest finish instead chooses $A$, then $B$, and attains two. A <counterexample> can refute a proposed <greedy-choice property> even when the rule succeeds on many other <inputs>.
Back to article page
