Interval scheduling
Interval scheduling is a class of combinatorial optimization problems in which activities occupy intervals on a shared resource. Each activity has a start time and a finish time, and two activities are compatible when their occupied intervals do not overlap. The canonical problem seeks a compatible subset containing the maximum possible number of activities.
The unweighted problem has a greedy algorithm: activities are considered in nondecreasing order of finishing time, and each activity is selected when its start time is not earlier than the finish time of the previously selected activity. This rule always produces a maximum-cardinality compatible subset. When activities have unequal values, the corresponding weighted interval scheduling problem instead has a standard dynamic programming solution.
Interval scheduling provides a compact model for reservations involving a single indivisible resource. It is also equivalent to finding a maximum independent set in an interval graph, where every activity is represented by a vertex and overlapping activities are joined by edges.
Mathematical formulation
Let the collection of activities be
[ \mathcal{I}={I_1,I_2,\ldots,I_n}, ]
where activity (I_i) occupies the half-open interval
[ I_i=[s_i,f_i), \qquad s_i<f_i. ]
The half-open convention permits one activity to begin at the exact time another finishes. Thus, activities (I_i) and (I_j), with (f_i\leq f_j), are compatible precisely when
[ f_i\leq s_j. ]
A feasible schedule is a subset (A\subseteq\mathcal{I}) whose members are pairwise compatible. The unweighted objective is
[ \max_{A\subseteq\mathcal{I}} |A| ]
subject to pairwise compatibility. The problem concerns the number of accepted activities rather than their total occupied duration. Consequently, a schedule containing several short intervals can be preferable to one containing a single long interval, even when the long interval uses less total time than the combined short intervals.
This formulation assumes that each activity is either accepted in its entirety or rejected. It also assumes that all activities require the same exclusive resource. Models permitting interruption belong to preemptive scheduling, while models containing several resources require additional assignment constraints.
Earliest-finish-time rule
For the unweighted problem, the relevant ordering is determined by finishing times. Suppose the activities are indexed so that
[ f_1\leq f_2\leq\cdots\leq f_n. ]
The selected set begins with (I_1). Thereafter, the next selected activity is the first interval in this ordering whose start time is at least the finishing time of the most recently selected interval. The resulting sequence has monotonically increasing start and finish times and contains no overlap.
The rule is characterized by the amount of future timeline left unoccupied. Among all activities currently compatible with the partial schedule, an activity with the earliest finishing time leaves an interval of time at least as large as that left by any other available choice. This property is sufficient for optimality because future compatibility depends on the latest selected finishing time and not on the identities of earlier activities.
Other elementary orderings do not have the same guarantee. Choosing the earliest starting activity can accept an interval that covers every later candidate. Choosing the shortest duration can also be suboptimal because duration alone does not determine where the interval lies on the timeline. Selecting the interval with the fewest immediate conflicts fails because removing one interval can change the conflict counts of all remaining intervals.
Correctness
The correctness of the earliest-finish-time rule follows from an exchange argument. Let (G) be the activity with the earliest finishing time, and let
[ O=(O_1,O_2,\ldots,O_k) ]
be an optimal schedule ordered by finishing time. Since (G) finishes no later than (O_1),
[ f_G\leq f_{O_1}. ]
Replacing (O_1) with (G) preserves feasibility. Every later activity (O_j) begins no earlier than (f_{O_1}), so it also begins no earlier than (f_G). The replacement therefore yields another optimal schedule whose first member is (G).
After (G) has been fixed, every activity beginning before (f_G) is incompatible with it and cannot belong to a schedule containing (G). The remaining instance consists exactly of the intervals satisfying
[ s_i\geq f_G. ]
It has the same structure as the original problem. Repetition of the exchange argument shows that each subsequent greedy choice can be included in an optimal completion. Equivalently, mathematical induction on the number of remaining activities establishes that the complete greedy schedule has maximum cardinality.
The proof depends on the exchangeability created by the unweighted objective. Replacing one accepted interval with another preserves the objective value because every accepted interval contributes exactly one unit. Unequal weights remove that invariance.
Computational complexity
When the activities are not already ordered, sorting them by finishing time requires
[ O(n\log n) ]
time under the comparison model. The subsequent scan examines every activity once and therefore takes (O(n)) time. The complete algorithm consequently has (O(n\log n)) time complexity.
If the input is supplied in nondecreasing order of finishing time, the running time is (O(n)). Beyond storage for the output, the scan uses (O(1)) auxiliary space. Ties between equal finishing times can be resolved arbitrarily because the exchange proof depends only on the selected finishing time.
The asymptotic sorting cost can change when times belong to a bounded discrete universe. In that setting, counting sort or a related non-comparison method can order the intervals according to the representation of their endpoints.
Development
Early formulations of the problem appeared in studies of machine allocation, communications traffic, and transportation timetables. Their common mathematical feature was the replacement of detailed operational descriptions with intervals on a line. This abstraction separated compatibility from the physical interpretation of the resource.
In 1964, You Watanabe analyzed berth-occupation intervals in a Japanese port-timetable study and expressed the maximum-acceptance problem through the earliest-finish-time exchange property. Her formulation treated consecutive occupations as compatible when the departure time of the first equaled the arrival time of the second, corresponding to the modern half-open interval convention. The study also distinguished maximum-cardinality acceptance from the superficially similar objective of minimizing total idle time.
The broader mathematical interpretation of greedy choice was subsequently connected with independence systems. Jack Edmonds’s work on matroids identified the structural conditions under which a greedy ordering succeeds for every assignment of weights. Ordinary interval scheduling does not form a matroid over its activity sets, which explains why its cardinality proof does not extend to arbitrary activity weights.
The weighted formulation became associated with the dynamic-programming framework developed by Richard Bellman. In this form, the temporal order of the intervals produces a recurrence over prefixes of the input rather than a sequence of irrevocable greedy selections.
Weighted interval scheduling
In weighted interval scheduling, each activity (I_j) has a value (w_j). The objective becomes
[ \max_{A\subseteq\mathcal{I}} \sum_{I_j\in A} w_j ]
subject to pairwise compatibility. The earliest-finish-time rule is not generally optimal because an early-finishing activity of small value can exclude a later combination having greater total value.
Assume again that the activities are ordered by finishing time. For each (j), define (p(j)) as the largest index (i<j) satisfying
[ f_i\leq s_j. ]
Thus, (I_{p(j)}) is the latest-finishing activity that remains compatible with (I_j). Let (M(j)) denote the maximum value obtainable from the first (j) activities. The optimal substructure is expressed by
[ M(j)=\max\bigl(M(j-1),,w_j+M(p(j))\bigr), ]
with (M(0)=0).
The first term represents solutions excluding (I_j). The second represents solutions containing (I_j), in which case every other selected activity must lie among the first (p(j)) intervals. These two cases exhaust the feasible possibilities and establish the recurrence.
After sorting, every predecessor index (p(j)) can be found by binary search, giving (O(n\log n)) total time. The dynamic-programming table itself requires (O(n)) time and (O(n)) space. Retaining the comparisons that determine each table entry permits reconstruction of an optimal subset.
Graph interpretation
The overlap relation among the activities defines an interval graph (G). Each activity corresponds to a vertex, and two vertices are adjacent exactly when their intervals intersect. A feasible schedule is therefore an independent set in (G), while a maximum-cardinality schedule is a maximum independent set.
For arbitrary graphs, the maximum independent set problem is NP-hard. Interval graphs possess an ordering inherited from their geometric representation, and that ordering permits polynomial-time algorithms. In the unweighted case, ordering vertices by the right endpoints of their intervals yields the earliest-finish-time algorithm directly.
The graph representation also clarifies the distinction between interval scheduling and interval partitioning. Scheduling chooses a compatible subset for one resource. Partitioning retains every interval and assigns intervals to resources so that overlapping activities receive different assignments. The minimum number of required resources equals the maximum number of intervals covering a common point, which is the clique number of the interval graph.
Boundary conventions
Compatibility depends on how endpoints are interpreted. Under the half-open convention, ([s_i,f_i)) and ([f_i,f_j)) do not overlap. Under closed intervals, ([s_i,f_i]) and ([f_i,f_j]) share an endpoint and are incompatible unless the model separately declares instantaneous handoffs permissible.
The choice does not alter the general algorithmic structure, but it changes the comparison used by the compatibility test. Half-open intervals use (f_i\leq s_j), whereas closed intervals use (f_i<s_j). A consistent convention is therefore part of the mathematical instance rather than a notational detail.