= Interval scheduling
{title2=$\max |S|$}
{wiki}
Given a <finite set> of jobs with fixed half-open <intervals> $[s_i,f_i)$, where $s_i<f_i$, choose a <subset> $S$ of <maximum> <cardinality>. Each job occupies one shared resource throughout its <interval>. A <feasible solution> has pairwise <disjoint> <intervals>: for distinct selected jobs $i,j$, either $f_i\leq s_j$ or $f_j\leq s_i$. Thus a finish and the next start may coincide. Every job has value one; occupied time is not the <objective function>.<6.046J Design and Analysis of Algorithms, Spring 2015/Lecture 1: Introduction>[6.046J Design and Analysis of Algorithms, Spring 2015; Printed p. 2, Interval Scheduling: fixed requests, one resource, compatibility with endpoint equality, maximum size]{ref}
Consider these six original jobs, with arbitrary time units:
$$
\begin{array}{c|rrrrrr}
\text{job}&A&B&C&D&E&F\\\hline
s_i&0&1&3&5&6&8\\
f_i&6&3&5&7&9&10
\end{array}.
$$
Job $B=[1,3)$ can be followed immediately by $C=[3,5)$ and $D=[5,7)$. Job $A=[0,6)$ conflicts with all three. Starting the resource earlier is therefore not automatically beneficial: one long commitment can displace several shorter requests.
The earliest-finish <greedy algorithm> uses a <sorting algorithm> to put jobs in <nondecreasing> finish time. Scan that order, accepting the first job and then each job whose start is at least the last accepted finish. Break finish-time ties arbitrarily; an empty <input> returns the <empty set>. For these jobs, the order and decisions are
$$
\begin{array}{c|rrrrrr}
\text{finish order}&B&C&A&D&E&F\\\hline
\text{decision}&\text{take}&\text{take}&\text{skip}&\text{take}&\text{skip}&\text{take}
\end{array}.
$$
After $B,C$, job $A$ starts before the current finish five and is rejected. Accept $D$; then reject $E=[6,9)$ because six is before seven. Finally accept $F=[8,10)$. The result is $S=\{B,C,D,F\}$, with <cardinality> four. Leaving $[0,1)$ idle makes room for more jobs.
By contrast, the earliest-start rule scans $A,B,C,D,E,F$. It accepts $A$, skips $B,C,D$, accepts $E$, and skips $F$. Its <feasible solution> $\{A,E\}$ contains only two jobs. Here $A$ and $E$ meet at time six and are compatible; $E$ and $F$ overlap on $[8,9)$.
\Image[/interval-scheduling-six-jobs-finish-versus-start.png]
{title=Earliest finish accepts four jobs; earliest start accepts two}
{description=The same six original <intervals> appear in both panels. Colored jobs are accepted and gray jobs rejected. A filled start and hollow finish depict a half-open <interval>; jobs meeting at an endpoint are compatible.}
There is also an elementary optimality certificate for this example. The four <subsets> $\{A,B\}$, $\{C\}$, $\{D,E\}$ and $\{F\}$ form a <partition of a set> of the jobs. A <feasible solution> takes at most one job from each group: $A,B$ overlap, as do $D,E$, and each other group is a <singleton>. Hence four is an <upper bound>, attained by $\{B,C,D,F\}$. Checking all $2^6=64$ <subsets> gives a unique optimum of size four: $\{B,C,D,F\}$.
The earliest-finish theorem states that this <greedy algorithm> maximizes job count for every finite instance of <interval scheduling>. For the <exchange argument>, let $q$ be the first job in an optimal <feasible solution> and $g$ an earliest-finishing job. Every later selected job $j$ satisfies
$$
f_g\leq f_q\leq s_j.
$$
Replace $q$ by $g$; compatibility and <cardinality> survive. The remainder must be optimal among jobs starting at or after $f_g$, or improving it would improve the whole selection. <Mathematical induction> on the smaller remaining instance, starting with the <empty set>, completes the outline.<Algorithms by Jeff Erickson/Greedy Algorithms>[Algorithms by Jeff Erickson; §4.2 Scheduling Classes, Lemma 4.3 and Theorem 4.4, printed pp. 163–164; endpoint equality is allowed by our half-open convention]{ref}
Why is the <algorithm> fast? Once sorted, each job is examined once, using only the last accepted finish to decide compatibility. The scan takes $O(n)$ time; comparison <sorting algorithms> give total <time complexity> $O(n\log n)$ for $n\geq2$, in <Big O notation>, assuming constant-cost endpoint comparisons. Already sorted <input> needs only the $O(n)$ scan.<6.046J Design and Analysis of Algorithms, Spring 2015/Lecture 1: Introduction>[6.046J Design and Analysis of Algorithms, Spring 2015; Printed pp. 2–4, earliest-finish rule, compatibility and first-job exchange; scan cost follows by counting one comparison per subsequent request]{ref}
The reason the shortcut is correct is stronger than "finishing sooner looks good": the <exchange argument> preserves every later job of a suitable optimum. This is the problem-specific fact that permits final decisions without exploring all <subsets>.
Back to article page
