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\le s_j$ or $f_j\le s_i$. Thus a finish and the next start may coincide. Every job has value one; occupied time is not the objective function.^[ref]

Consider these six original jobs, with arbitrary time units: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 areAfter $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)$.

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$ satisfiesReplace $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.^[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\ge 2$, in Big O notation, assuming constant-cost endpoint comparisons. Already sorted input needs only the $O(n)$ scan.^[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.

A greedy-choice property says that some optimal feasible solution contains the locally selected choice. Together with optimal substructure in the remaining instance, it allows repeated commitments. An exchange argument often establishes this property.^[ref]

For interval scheduling, a safe first choice need not belong to every optimal feasible solution. When several optima exist, a commitment may exclude one while retaining another. The useful loop invariant is that the accepted prefix can still be extended to an optimum. Merely keeping the accepted intervals compatible proves feasibility, which is a weaker claim.

Online text: www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch6.pdf

Chapter 6 of Graph Theory by Reinhard Diestel, by Reinhard Diestel. Springer publishes the book; the author’s University of Hamburg site hosts the preview. No edition, publication year or revision date is established from this preview.

Cited passages: Chapter 6 opening, printed p. 155 (PDF p. 1): signed amounts and nonterminal conservation.; §6.2, printed p. 158 (PDF p. 4): independently specified orientation capacities, conditions F1/F2′/F3 and source/sink cut definition.; §6.2, printed p. 159 (PDF p. 5): Proposition 6.2.1, cancellation proof, total-value definition, footnote 4 on negative values, capacity upper bound and Theorem 6.2.2..

The upper part of the terrestrial atmosphere includes regions where ionization makes the response to electromagnetic waves depend strongly on mobile electrons. The ionosphere describes that electrical structure; its boundaries need not coincide with the boundaries defined by temperature in the mesosphere and thermosphere.

A geometric envelope is a curve tangent to the members of a smoothly varying family of curves. For a regular implicit family $F(x,y,s)=0$, candidate contact points also satisfy the partial derivative condition ${\partial }_{s}F=0$; regularity is needed to turn these candidates into an actual envelope. The Mach cone is a three-dimensional analogue for expanding spheres.

Chapter 6 of Genomes, 2nd edition by Terence A. Brown. Terence A. Brown, printed as T. A. Brown, is the whole-book author; no independent chapter-author byline is established. The second edition is dated 2002. NCBI Bookshelf hosts the online text.

Online text: www.ncbi.nlm.nih.gov/books/NBK21117/

Cited passages: Official indexed chapter text, section 6.1.1, Chain termination sequencing in outline; Figure 6.1 and Figure 6.2 captions; single-nucleotide resolution and bottom-to-top autoradiographic interpretation; Technical Note 6.1, polyacrylamide versus agarose separation.

A selectable marker is a gene or other inherited feature that permits recovery of carriers under specified growth conditions. Selection for a marker does not identify every other nucleotide sequence in its carrier.

A theorem giving conditions under which some geodesic is incomplete. The Penrose singularity theorem is one example.