Greedy Interval Scheduling solves the Interval Scheduling problem.
The goal is to select as many non-overlapping intervals as possible. A natural local rule is: always take the interval that finishes earliest. Intuitively, finishing sooner leaves the largest remaining “window” for whatever comes next. This is a classic Greedy move: make an irrevocable, locally optimal choice and never look back. The optimality of this greedy rule can be proven using a standard exchange argument.
Greedy-Choice (Exchange) Argument. Let E be the interval with the earliest finish time. Suppose some optimal schedule O does not start with E, but with a different interval X. Because E finishes no later than X, we can swap X out and start with E instead; the rest of O still fits (or fits at least as well) after E. Thus there exists an optimal schedule that begins with E. After taking E, the problem reduces to the same question on the intervals that start at or after finish(E). By induction on the number of remaining intervals, repeatedly taking the earliest-finishing interval is optimal.
Why not another rule? If the goal is to fit as many intervals as possible, why not pick the ones that start earliest, or the shortest ones? It turns out those seemingly natural ideas can block better options down the line. Choosing by earliest finish is the only rule that always leaves room for the rest, as the exchange argument confirms.
Algorithm outline. The idea is simple: sort the intervals by finish time, then sweep through them once. For each interval, ask whether it begins after the last selected one ends—if it does, include it; otherwise, skip it. Here is the algorithm in pseudocode:
Intervals (unsorted):
\(\small A(6,10),\ B(0,6),\ C(5,9),\ D(2,13),\ E(5,7),\ F(3,5),\ G(12,14),\ H(8,12),\ I(8,11),\ J(1,4),\ K(3,8) \).
Sorted by finish time:
\(\small J(1,4),\ F(3,5),\ B(0,6),\ E(5,7),\ K(3,8),\ C(5,9),\ A(6,10),\ I(8,11),\ H(8,12),\ D(2,13),\ G(12,14) \).
Selected set: \( \{E, G, I, J\} \) (4 intervals).
Tie-handling note. If two intervals share the same finish time, either is safe; picking the later-starting one can reduce “wasted” slack before it, but correctness does not depend on this tie-break.
This fits the greedy technique: we commit to the earliest-finishing interval at each step (a local optimum), and an exchange argument shows that doing so never harms the possibility of a globally optimal schedule. It can also be viewed as an instance of transform-and-conquer—the initial presorting of intervals by finish time transforms the data into an order where the greedy rule becomes both natural and provably optimal.
The following demo gives a more graphical view of the algorithm so you can see more clearly why the strategy works.
The core idea is the same across all three implementations: sort intervals by nondecreasing finish time, then sweep through them, keeping an interval whenever its start is at or after the end of the last chosen interval. Each version maintains a running variable \( \textit{currentEnd} \) (or \( \textit{current_end} \)) and a count of chosen intervals. These snippets intentionally return only the number of non-overlapping intervals, not the schedule itself; returning the actual intervals is left to the reader as a small extension. We assume valid inputs with \( \textit{start} \le \textit{end} \). Tie-handling in these implementations is not explicit: Java (\( \texttt{Arrays.sort} \) on \( \texttt{Comparable} \)) and Python (\( \texttt{list.sort} \)) are stable and will preserve the input order among equal finish times; C++ uses \( \texttt{std::sort} \), which is not stable, so equal-finish intervals may appear in any order.
Interval class implementing
Comparable<Interval> so that Arrays.sort
orders intervals by finish time. A simple loop keeps an interval when
\( \textit{start} \ge \textit{currentEnd} \), incrementing the count and updating
\( \textit{currentEnd} \).struct Interval and a
compare function on end, passed to
std::sort for the presort. The greedy loop applies the same rule
\( \textit{start} \ge \textit{currentEnd} \) to decide which intervals to keep.list.sort using a small key function \( \textit{end(iv)}=iv[1]\).
This function simply returns the second point in the pair.
The single-pass loop selects intervals using the same
\( \textit{start} \ge \textit{current_end} \) test.class Interval implements Comparable<Interval> {
int start, end;
Interval(int s, int e) { start = s; end = e; }
@Override
public int compareTo(Interval other) {
return Integer.compare(this.end, other.end); // ascending by finish time
}
}
int intervalSchedule(Interval[] intervals) {
// Handle empty input early
if (intervals.length == 0) return 0;
// Sort by finish time (ascending)
Arrays.sort(intervals);
// Seed from the first (earliest-finishing) interval
int count = 1;
int currentEnd = intervals[0].end;
for (int i = 1; i < intervals.length; i++) {
Interval iv = intervals[i];
if (iv.start >= currentEnd) {
count++;
currentEnd = iv.end;
}
}
return count;
}#include <algorithm>
#include <vector>
struct Interval {
int start, end;
};
bool compare(const Interval& a, const Interval& b) {
return a.end < b.end; // ascending by finish time
}
int intervalSchedule(std::vector<Interval>& intervals) {
// Handle empty input early
if (intervals.empty()) return 0;
std::sort(intervals.begin(), intervals.end(), compare);
int count = 1; // take the first (earliest-finishing) interval
int currentEnd = intervals[0].end; // seed from its end time
int n = intervals.size();
for (int i = 1; i < n; ++i) {
if (intervals[i].start >= currentEnd) {
++count;
currentEnd = intervals[i].end;
}
}
return count;
}def end(iv):
return iv[1]
def interval_schedule(intervals):
# Handle empty input early
if not intervals:
return 0
# Sort by finish time (ascending)
intervals.sort(key=end)
# Seed from the first (earliest-finishing) interval
count = 1
current_end = intervals[0][1]
for start, end_ in intervals[1:]:
if start >= current_end:
count += 1
current_end = end_
return countThese implementations are intentionally minimal to emphasize the greedy structure and they only determine how many intervals can be scheduled. To return the schedule, record each selected interval (or its index) when chosen and return that list instead of just the count. This change does not affect asymptotic time or space complexity. If desired, you can also standardize tie-breaking (e.g., prefer later starts among equal finishes) without changing correctness.
Time Complexity: The presorting step dominates the runtime. Sorting \( n \) intervals by finish time takes \( O(n \log n) \), while the greedy sweep that follows runs in \( O(n) \). Therefore, the overall time complexity is \( O(n \log n) \).
Space Complexity: When sorting is done in place, only a few scalar variables are needed (such as \( \textit{currentEnd} \) and the count), giving \( O(1) \) extra space. If the sort produces a new list or array, the space cost rises to \( O(n) \). Returning the actual intervals rather than just their count does not change asymptotic time, but it requires storing up to \( O(n) \) selected intervals—still linear in space.
There is not much to improve upon with this algorithm, other than returning the intervals in the solution. However, there are a wide variety of scheduling problems.