Greedy Interval Scheduling

Given a pile of intervals, keep as many as possible with no two overlapping. The obvious greedy choices are wrong in an instructive way:

Earliest start? One interval starting at time 0 and running all day blocks everything.
Shortest duration? A short interval planted in the middle can break two long compatible ones.

The choice that is optimal: always keep the interval that finishes earliest. Finishing early leaves the most room for everything after it, and that intuition can be turned into a proof.

This page is as much about the exchange argument as the code, because “sort by end” is three lines and “why is that optimal?” is the actual interview question.

What you’ll learn

The sort-by-end template, and the one comparison it hinges on.
The exchange argument — how to prove a greedy choice is safe.
Why the same code answers “erase the fewest”, “shoot the fewest arrows”, and “longest chain”.
The >> vs >=>= decision, which is the only thing distinguishing several of these problems.
Three real LeetCode problems solved in the browser: 435, 452, 646.

The cue

The template

max_non_overlapping.py

def max_non_overlapping(intervals):
    if not intervals:
        return 0
 
    intervals.sort(key=lambda x: x[1])       # sort by END time
    kept = 1
    last_end = intervals[0][1]
 
    for start, end in intervals[1:]:
        if start >= last_end:                # compatible: starts after we finished
            kept += 1
            last_end = end                   # commit to this one
        # else: overlaps -- skip it, keep the earlier-finishing one
    return kept
 
 
print(max_non_overlapping([[1, 2], [2, 3], [3, 4], [1, 3]]))   # 3

max_non_overlapping.py

def max_non_overlapping(intervals):
    if not intervals:
        return 0
 
    intervals.sort(key=lambda x: x[1])       # sort by END time
    kept = 1
    last_end = intervals[0][1]
 
    for start, end in intervals[1:]:
        if start >= last_end:                # compatible: starts after we finished
            kept += 1
            last_end = end                   # commit to this one
        # else: overlaps -- skip it, keep the earlier-finishing one
    return kept
 
 
print(max_non_overlapping([[1, 2], [2, 3], [3, 4], [1, 3]]))   # 3

$O(n \log n)$ for the sort, $O(n)$ for the scan, $O(1)$ extra space.

That is the entire pattern. Everything below is either a proof of it or a rewording of it.

Why earliest-finish is optimal — the exchange argument

This is the reasoning interviewers are fishing for. Learn the shape; it transfers to every greedy proof.

Let gg be the interval finishing earliest overall, and let OPTOPT be any optimal solution.

If OPTOPT already contains gg, there is nothing to show.
Otherwise, let ff be the interval in OPTOPT that finishes earliest. By definition of gg, we know end(g) <= end(f)end(g) <= end(f).
Swap ff for gg in OPTOPT. Is the result still valid? Every other interval in OPTOPT starts at or after end(f)end(f), and end(g) <= end(f)end(g) <= end(f), so they all start at or after end(g)end(g) too. No new overlap is created.
The swap keeps the size identical, so the modified solution is also optimal — and it contains gg.

So there is always an optimal solution containing the earliest-finishing interval. Take gg, discard everything that overlaps it, and recurse on the rest — each step is safe by the same argument.

The variant map

All four of these are the same scan. Only the comparison and the returned quantity change.

Problem	Sort by	Keep when	Return
435 Erase overlaps	end	`start >= last_endstart >= last_end`	`len - keptlen - kept`
452 Burst balloons	end	`start > last_endstart > last_end`	`keptkept` (arrows)
646 Longest chain	end	`start > last_endstart > last_end`	`keptkept`
1024 Video stitching	start	(different — interval covering)	jumps

Practice — real LeetCode problems

LC 435 — Non-overlapping Intervals · Medium

Problem. Given an array of intervals, return the minimum number you must remove so that the rest are non-overlapping.

Constraints. 1 <= len(intervals) <= 10^51 <= len(intervals) <= 10^5, -5 * 10^4 <= start < end <= 5 * 10^4-5 * 10^4 <= start < end <= 5 * 10^4.

Examples. [[1,2],[2,3],[3,4],[1,3]][[1,2],[2,3],[3,4],[1,3]] gives 11 (remove [1,3][1,3]) · [[1,2],[1,2],[1,2]][[1,2],[1,2],[1,2]] gives 22 · [[1,2],[2,3]][[1,2],[2,3]] gives 00

Editorial — approach, complexity, follow-ups

The reframe is the insight: minimising removals is maximising retentions. Once stated that way it is the standard interval-scheduling problem, and the answer is len(intervals) - max_keptlen(intervals) - max_kept.

Time $O(n \log n)$ . Space $O(1)$ beyond the sort.

[[1,100],[2,3],[4,5]][[1,100],[2,3],[4,5]] returning 11 is the case that punishes sorting by start: you must drop the long [1,100][1,100] and keep the two short ones. A sort-by-start solution keeps [1,100][1,100] and reports 22 removals.

[[1,2],[2,3]][[1,2],[2,3]] returning 00 confirms the >=>= — half-open intervals that touch are compatible.

There is also an $O(n^2)$ DP solution (longest non-overlapping subsequence by end time) which is worth naming to show you know greedy is not the only route — but it TLEs at $n = 10^5$ , and the exchange argument is what justifies the faster answer.

Follow-ups you should expect: “Prove the greedy is optimal” — the exchange argument above; this is the most likely follow-up. “What if intervals have weights and you want maximum total weight?” — greedy fails; it becomes weighted interval scheduling, solved by DP with binary search in $O(n \log n)$ . That is a genuinely important boundary to know. “Return which intervals to remove?” — record the skipped ones during the scan.

LC 452 — Minimum Number of Arrows to Burst Balloons · Medium

Problem. Balloons are given as [start, end][start, end] on the x-axis. An arrow shot straight up at xx bursts every balloon with start <= x <= endstart <= x <= end. Return the minimum number of arrows needed to burst them all.

Constraints. 1 <= len(points) <= 10^51 <= len(points) <= 10^5, -2^31 <= start <= end <= 2^31 - 1-2^31 <= start <= end <= 2^31 - 1.

Examples. [[10,16],[2,8],[1,6],[7,12]][[10,16],[2,8],[1,6],[7,12]] gives 22 · [[1,2],[3,4],[5,6],[7,8]][[1,2],[3,4],[5,6],[7,8]] gives 44 · [[1,2],[2,3],[3,4],[4,5]][[1,2],[2,3],[3,4],[4,5]] gives 22

Editorial — approach, complexity, follow-ups

Sort by end. Shoot the first arrow at points[0][1]points[0][1] — the earliest end. Any balloon overlapping that position is burst for free, so the arrow is never wasted, and placing it any further right could miss the first balloon. Then skip forward past everything already burst and repeat.

Time $O(n \log n)$ . Space $O(1)$ .

[[1,2],[2,3],[3,4],[4,5]][[1,2],[2,3],[3,4],[4,5]] giving 22 is the inclusive-endpoint test. Sorted by end, the first arrow goes at 22, bursting [1,2][1,2] and [2,3][2,3] (because 22 is inside [2,3][2,3]). The next unburst balloon is [3,4][3,4], so the second arrow at 44 bursts [3,4][3,4] and [4,5][4,5]. Two arrows.

Using >=>= instead of >> would demand a new arrow for [2,3][2,3] and return 44 — a wrong answer produced by code that otherwise looks identical to LC 435. This is the clearest example on the site of why endpoint conventions deserve an explicit question.

Follow-ups you should expect: “Why shoot at the end and not the middle?” — the end is the rightmost position still guaranteed to hit the current balloon, so it maximises how many later balloons are also caught. “Return the arrow positions?” — collect lastlast each time you increment. “What if arrows had a width?” — becomes an interval-covering problem, closer to LC 1024.

LC 646 — Maximum Length of Pair Chain · Medium

Problem. Given pairs where pairs[i] = [left, right]pairs[i] = [left, right] and left < rightleft < right, a pair [c, d][c, d] can follow [a, b][a, b] if b < cb < c. Return the length of the longest chain you can form, choosing and ordering pairs freely.

Constraints. 1 <= len(pairs) <= 10001 <= len(pairs) <= 1000, -1000 <= left < right <= 1000-1000 <= left < right <= 1000.

Examples. [[1,2],[2,3],[3,4]][[1,2],[2,3],[3,4]] gives 22 ([1,2] -> [3,4][1,2] -> [3,4]) · [[1,2],[7,8],[4,5]][[1,2],[7,8],[4,5]] gives 33

Editorial — approach, complexity, follow-ups

Exactly LC 435’s algorithm with a strict comparison. Because pairs may be reordered freely, “longest chain” is precisely “largest set of mutually non-overlapping pairs” — any such set can be laid out in end order to form a chain.

Time $O(n \log n)$ . Space $O(1)$ .

Initialising count = 0count = 0 and last = float("-inf")last = float("-inf") lets the loop handle the first pair with no special case, which is tidier than seeding from pairs[0]pairs[0]. It also handles the negative coordinates in the third test case correctly — seeding last = 0last = 0 would break there, and that case exists specifically to catch it.

[[1,2],[2,3],[3,4]][[1,2],[2,3],[3,4]] giving 22 is the strictness check: [1,2][1,2] cannot be followed by [2,3][2,3] because 2 < 22 < 2 is false. Contrast LC 435, where those two are compatible. The same input, a different answer, one character of difference in the code.

There is a well-known $O(n^2)$ DP for this (sort by first element, then longest-increasing-subsequence style), and LeetCode’s own editorial presents it. Worth mentioning to show range, but greedy is $O(n \log n)$ and provably optimal.

Follow-ups you should expect: “Return the chain itself?” — collect pairs as you accept them. “What if the rule were b <= cb <= c?” — switch to >=>=, and it becomes LC 435. “What if each pair had a value and you wanted maximum total?” — greedy fails; weighted interval scheduling via DP + binary search.

LeetCode problem set

#	Problem	Difficulty	The twist
435	Non-overlapping Intervals	Medium	Maximise kept, then subtract; `>=>=` for half-open
452	Minimum Number of Arrows to Burst Balloons	Medium	Inclusive endpoints, so the comparison is strict `>>`
646	Maximum Length of Pair Chain	Medium	Strict chain rule; seed `lastlast` at $-\infty$ for negatives
1024	Video Stitching	Medium	Covering, not selecting — sort by start and jump-extend

Interview follow-ups

They ask	What they’re checking	The answer
“Why sort by end?”	Whether you can prove it	The exchange argument: any optimal solution can swap its earliest-finishing interval for the globally earliest-finishing one without breaking validity or changing size
“Why not by start, or by duration?”	Whether you tested it	`[[1,100],[2,3],[4,5]][[1,100],[2,3],[4,5]]` breaks sort-by-start; `[[1,5],[4,6],[5,9]][[1,5],[4,6],[5,9]]` breaks sort-by-duration
”`>>` or `>=>=`?”	Attention to conventions	Half-open intervals use `>=>=` (touching is fine); inclusive endpoints use `>>`
“What if intervals have weights?”	Knowing where greedy dies	Greedy fails; weighted interval scheduling needs DP with binary search, $O(n \log n)$
“Can you do it without sorting?”	Lower bounds	Not in general — $\Omega(n \log n)$ by reduction from sorting, unless coordinates are bounded and you can bucket
“Which intervals did you keep?”	Bookkeeping	Collect them during the scan instead of only counting
“Covering instead of selecting?”	Distinguishing greedies	Sort by start and extend furthest — LC 1024, a different pattern

Edge-case checklist

Single interval — answer 11 kept / 00 removed / 11 arrow.
All identical — [[1,2],[1,2],[1,2]][[1,2],[1,2],[1,2]]; only one survives.
Touching endpoints — [[1,2],[2,3]][[1,2],[2,3]]; the >=>= vs >> test, and it differs by problem.
One interval swallowing all others — [[1,100],[2,3],[4,5]][[1,100],[2,3],[4,5]]; breaks sort-by-start.
Negative coordinates — seed lastlast at float("-inf")float("-inf"), never 00.
Already sorted input — no special handling, but a plausible test.
Empty input — return 00; guard before intervals[0]intervals[0].
Fully nested intervals — sorting by end naturally prefers the inner one, which is correct.

Recap

Sort by end time and greedily keep every compatible interval. That is the whole algorithm: $O(n \log n)$ , $O(1)$ space.
Finishing earliest leaves the most room for what follows, and the exchange argument turns that intuition into a proof. Be ready to give it — it is the likeliest follow-up.
“Remove the fewest” is “keep the most” in disguise: answer len - keptlen - kept.
435, 452 and 646 are the same scan. The differences are >=>= versus >> (endpoint conventions) and what you return.
Greedy dies as soon as intervals carry weights — that is DP territory.
Selecting a non-overlapping subset (this page) is not the same as covering a range (LC 1024). Sorting by end is right for the first and wrong for the second.

Next: Greedy Reachability and Jumps — the covering-style greedy, where you track how far you can get rather than which items you keep.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Greedy Interval Scheduling

What you’ll learn

The cue

The template

Why earliest-finish is optimal — the exchange argument

The variant map

Practice — real LeetCode problems

LC 435 — Non-overlapping Intervals · Medium

LC 452 — Minimum Number of Arrows to Burst Balloons · Medium

LC 646 — Maximum Length of Pair Chain · Medium

LeetCode problem set

Interview follow-ups

Edge-case checklist

Recap

Was this page helpful?