Greedy algorithm

A greedy algorithm builds a feasible solution by repeatedly committing to a locally preferred next choice. Each commitment is final: the algorithm does not revisit it when later choices become available. In mathematical optimization, the important question is whether those commitments can still attain the best objective function value.

For example, a shared telescope can accept several observation requests with fixed time slots. In interval scheduling, every completed request counts equally, and overlapping requests cannot both be accepted. Choosing the request that finishes earliest leaves the resource available sooner. The example below turns that intuition into a precise rule, then shows why choosing the earliest start or shortest duration can lose jobs.

Greedy algorithms are attractive because a single pass can replace a search through many candidate subsets. However, "locally best" is only a design proposal. A problem-specific greedy-choice property, often established by an exchange argument, must connect the local decision to the actual objective function. The largest-individual-value rule in the 0-1 knapsack problem fails; Dijkstra's algorithm needs its nonnegative-edge assumptions. A rule's success in one optimization task does not justify it in another.

Given finitely many nonempty closed intervals $[s_i,e_i]$, choose as few points as possible so that each interval contains a chosen point. An optimal greedy algorithm repeatedly chooses the smallest end of an uncovered interval. After choosing $t$, any still uncovered interval starts strictly after $t$, since its end cannot be smaller than $t$. Thus the intervals whose ends trigger successive choices are pairwise disjoint. Every feasible point set needs a separate point in each triggering interval, proving that the greedy point set is optimal. Sorting by end and scanning takes $O(n\log n)$ time. The inclusion of endpoints means an interval starting at the last chosen point is already covered.

Repeatedly removing a longest strictly increasing subsequence need not minimise the number of increasing subsequences in a partition. In $(2,4,1,3)$, removing $(2,3)$ leaves the decreasing pair $(4,1)$, for three subsequences overall. The partition $(2,4)$ and $(1,3)$ uses only two and is optimal because the original sequence is not increasing.

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.

An exchange argument modifies an optimal feasible solution to include a desired choice while preserving feasibility and not worsening its objective function value. The modification need not strictly improve the optimum; equality suffices.^[ref]

For interval scheduling, the exchange replaces the first selected job with an earliest-finishing job. Its safety comes from the finish-time inequality below. Replacing a job with a shorter one has no such guarantee: it might move the occupied interval into the middle of two useful jobs, as the shortest-duration interval scheduling counterexample shows.

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.

In this separate three-job example, labels $A,B,C$ denote new jobs: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.

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.

Weighted interval scheduling assigns each job a reward $w_i$ and maximizes their sum over compatible jobs. Earliest finish can fail for this different objective function; dynamic programming can compare alternatives.^[ref]

For a separate two-job example, let $X=[0,2)$ have reward one and $Y=[1,3)$ reward ten. Earliest finish accepts $X$ and rejects $Y$, earning one; the optimum accepts $Y$, earning ten. Replacing $Y$ by $X$ preserves job count but loses reward. Thus the interval scheduling exchange argument proves the unit-value theorem only: its preserved quantity must match the intended objective function.