One conference room. Nine candidate meetings on the same Tuesday. Facilities wants as many as will fit without two occupying the room at once. Product enumerates subsets: try every combination, skip any pair that overlaps, keep the largest. Nine meetings is 512 subsets. A week’s optional slots is not a spreadsheet.
The same job shows up as “how many jobs can this machine run if only one runs at a time.” Still every subset. Still an exponential bill for a question that only needs the order that frees the room soonest.
Sort by finish time. Take a candidate if its start is ≥ the last accepted finish. Throw the rest away. You do not merge overlapping meetings into one longer block. You reject a candidate that would still occupy the room. The output is a subset of the original ranges.
This post is that greedy. Families and the catalog live on the Algorithms Roadmap. Merge Intervals collapsed occupancy on a freeze calendar — a different output. Weighted meetings (a board session worth more than three standups) are a different job too. This post only maximizes the count.
Not Merge Intervals
Merge Intervals keeps every occupied instant. Nested and overlapping ranges disappear as rows. The union on the timeline stays the same size. You sort by start and extend an end with max.
This post throws ranges away. Two meetings that overlap are not one longer meeting; one of them loses the room. You sort by finish. You never extend an end.
| Job | Output | Order you sort |
|---|---|---|
| Merge Intervals | Occupied union, collapsed | By start, then sweep and extend |
| Interval Scheduling | A subset of the original ranges | By earliest finish |
Do not merge [9, 12) and [11, 14) into [9, 14) when the product is one room. That invents a meeting nobody booked and hides the conflict. Collapse occupancy when you need busy-vs-free. Schedule when you need a maximum set of originals.
Sort by finish, take if it fits
Two steps.
- Sort the meetings by
end(tie-break onstartfor a deterministic order). - Scan left to right. Keep
lastFinish. Take the next meeting ifstart ≥ lastFinish; then setlastFinishto that meeting’send. Otherwise skip it.
After sorting, the next finish is the soonest remaining end. Taking it frees the room as early as any remaining candidate can. Everything that still overlaps that choice is discarded. Everything that starts at or after that finish is still available.
You do not sort by start. An early-starting long all-hands would be accepted first and would block every short meeting that could have stacked after a 30-minute standup.
Half-open [start, end) matches the freeze-calendar encoding from Merge Intervals. The take predicate is the one the title named: take when next.start ≥ lastFinish. A meeting that ends at 11:00 and one that starts at 11:00 share no instant. The room is free at the finish.
Note: Closed [start, end] that must not share an endpoint uses >. Mixing closed and half-open in one list is how you accept a pair that still collides at a midnight. Pick one encoding and convert at the boundary.
A walk: nine candidates, six keep the room
Same Tuesday, minutes from midnight. Half-open. Take on ≥.
input (unsorted):
All-hands [540, 720) 09:00-12:00
Standup [540, 570) 09:00-09:30
Design [570, 660) 09:30-11:00
1:1 [600, 630) 10:00-10:30
Lunch [660, 720) 11:00-12:00
Customer [720, 780) 12:00-13:00
Retro [780, 870) 13:00-14:30
Interview [810, 900) 13:30-15:00
Demo [870, 930) 14:30-15:30
after sort by finish:
Standup [540, 570)
1:1 [600, 630)
Design [570, 660)
All-hands [540, 720)
Lunch [660, 720)
Customer [720, 780)
Retro [780, 870)
Interview [810, 900)
Demo [870, 930)
scan (lastFinish starts at −∞):
Standup 540 ≥ −∞ take lastFinish = 570
1:1 600 ≥ 570 take lastFinish = 630
Design 570 ≥ 630 skip
All-hands 540 ≥ 630 skip
Lunch 660 ≥ 630 take lastFinish = 720
Customer 720 ≥ 720 take lastFinish = 780
Retro 780 ≥ 780 take lastFinish = 870
Interview 810 ≥ 870 skip
Demo 870 ≥ 870 take lastFinish = 930
kept (original ranges):
Standup, 1:1, Lunch, Customer, Retro, Demo — 6 meetingsDesign overlaps the 1:1. All-hands overlaps everything before lunch. Interview overlaps the retro. None of those three are collapsed into a longer block. They are gone.
If you had taken All-hands first (earliest start, longest occupancy), the morning is one meeting, then Customer, Retro, Demo — four. The long freeze of the room is exactly why earliest start is the wrong greedy.
Empty input emits nothing. One meeting emits itself. Unsorted input is legal; the procedure sorts.
Why earliest finish
Any optimal first meeting can be swapped for the globally earliest-finishing one without shrinking the set.
Let f be the meeting that finishes first among all candidates. Let OPT be some maximum compatible set, ordered by finish, and let g be OPT’s first meeting. Then f ends no later than g. Every later meeting in OPT starts at or after g’s finish, hence at or after f’s finish, so it does not overlap f. Replace g with f: same size, still compatible. There is an optimal schedule whose first meeting is the one that frees the room soonest. Repeat on whatever remains with start ≥ f.end.
That is the greedy-choice property. You never need to revisit a skip.
Earliest start fails because a long early block occupies the suffix many short meetings could have stacked. Shortest duration fails on a short meeting that sits in the overlap of two longer, non-overlapping ones: taking the short yields 1; taking the two longs yields 2.
shortest-duration trap:
[0, 3) [3, 6) [2, 4)
durations 3, 3, 2
shortest takes [2, 4) -> 1
earliest finish takes [0, 3) then [3, 6) -> 2Note: Ties on finish time do not change the count. Either meeting with the same end leaves the same lastFinish. Tie-break on start only so the subset is deterministic.
Java: sort once, then a linear yes/no
A range is two endpoints. The same record Merge Intervals used is enough. There is no java.util.IntervalScheduler.
record Interval(int start, int end) {
Interval {
if (start > end) {
throw new IllegalArgumentException("start > end");
}
}
}
static List<Interval> schedule(List<Interval> meetings) {
List<Interval> sorted = new ArrayList<>(meetings);
sorted.sort(Comparator.comparingInt(Interval::end)
.thenComparingInt(Interval::start));
List<Interval> kept = new ArrayList<>();
int lastFinish = Integer.MIN_VALUE;
for (Interval m : sorted) {
if (m.start() >= lastFinish) {
kept.add(m);
lastFinish = m.end();
}
}
return kept;
}The objects in kept are the originals (or equal records). You did not allocate a merged [min start, max end]. Copying before sort is the safer default; do not mutate the caller’s list unless that is the contract.
Note: Integer.MIN_VALUE as the initial lastFinish makes the first candidate always legal. An empty list returns empty. If the domain uses Instant, the same loop compares with !m.start().isBefore(lastFinish) for half-open ≥.
Weighted is a different job
If each meeting has a value and the objective is maximum total value, earliest finish is the wrong greedy. A three-hour board session can beat three standups on dollars and lose on count — or the reverse. That is weighted interval scheduling, a DP recurrence on intervals already sorted by finish: for each i, take v_i plus the best that ends before i starts, or skip i. It is not this loop with a value field bolted on.
Do not run unweighted earliest-finish and call the sum of values “close enough.” The exchange argument above is about cardinality, not weight.
Huffman, 0/1 knapsack, and search-with-undo are other Wave 6 names on the roadmap. They are not a lab in this post.
Complexity
| What | Cost | Why |
|---|---|---|
| Time | O(n log n) | Sort by finish; the scan is O(n) |
| Extra space | O(n) | Copy to sort, plus the kept subset (worst case: none overlap) |
| Brute subsets | O(2^n · n) | Every combination, then overlap checks |
| Output | O(k) | k original ranges, k ≤ n |
The input list is O(n) whoever owns it. Interval Scheduling does not allocate a DP table for the unweighted count. Sort by end, one pass of yes/no, originals kept or thrown. A correct subset enumerator is still the wrong default on a week’s optional slots.
When not to schedule this way
Skip earliest-finish when the job is not “maximum count of non-overlapping intervals from a known list”:
- You needed occupancy, not a subset. Collapse overlapping freezes with Merge Intervals. Do not throw a nested drill away if it still covers time.
- Meetings have weights. Weighted interval scheduling is DP. This greedy is silent on value.
- You must host everyone. Minimum rooms (or machines) so no meeting is rejected is a different greedy: sort by start, track how many are live — often a min-heap of finish times. One room plus a subset is this post; “how many rooms?” is not.
- A required meeting cannot be dropped. Pin it, then run earliest-finish on what remains with
start ≥that finish (andend ≤that start). The unconstrained sort does not know about must-haves. - Online arrivals. The proof needs the full list. A request that appears after you already accepted a later finish cannot be exchanged in. Treat online admission as a different bill.
- Point queries on a huge static set. “Which original ids contain this timestamp?” is an interval tree (or a segment tree on compressed endpoints), not a subset picker. That layout is a later catalog job, not this scan.
Unweighted, offline, one resource, maximize how many originals fit — that is the job. Anything else is a different procedure that may call this sort.
Cheat sheet
Job: maximum-cardinality non-overlapping subset (one resource)
Invariant: sorted by finish; lastFinish is when the room next frees
Predicate: take when next.start ≥ lastFinish (half-open: touch is OK)
Reject: overlapping candidates are thrown, not merged
Encoding: pick half-open [start, end) or closed; do not mix
Time: O(n log n) sort + O(n) scan
Space: O(n) copy + O(k) output
Not this: Merge Intervals (union); weighted (DP); min rooms
JDK: List.sort / Arrays.sort by end; no IntervalScheduler classDo:
- Sort by finish once, then take or skip; never extend an end with
max. - Return original ranges. The kept list is a subset, not a collapsed union.
- Use half-open
[start, end)with≥so a finish and a next start can share the clock time without sharing an instant.
Don’t:
- Enumerate every subset once
nis a calendar, not a puzzle. - Sort by start (or by duration) and claim the same greedy-choice proof.
- Collapse
[9, 12)and[11, 14)and call it scheduling. - Bolt a
valuefield onto this loop and skip the weighted DP.
Wrap-up
Interval Scheduling replaces “every compatible subset” with one decision per meeting in finish order: take it if the room is already free, otherwise throw it away. Earliest finish is legal because any optimal first pick can be swapped for the globally earliest-finishing interval without losing count — it frees the room soonest. The bill is the sort, then a linear yes/no. The output objects are the ones you started with.
Merge Intervals was the occupancy collapse; this is the subset. Weighted value is DP. When the next job is a search whose later choices depend on what you just committed, that is backtracking — start from the Algorithms Roadmap if you need the family names again.