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

You are looking at greedy interval scheduling when…

• “Maximum number of non-overlapping” intervals — 435, 646.
• “Minimum number to remove” so the rest do not overlap. Same problem: total - max_kept.
• “Minimum number of arrows/shots/taps” to cover or pierce everything — 452, 1024.
• “Longest chain” where each link must start after the previous ends — 646.
• Each interval is kept or dropped, and you want to optimise the count.

The distinction from sweep line: sweeping counts how many overlap simultaneously. Scheduling selects a subset. If the answer is “how many rooms”, sweep. If it is “how many meetings can I attend”, schedule.

Visual intuition

Sorted by end time, not start. That choice is the whole insight:

intervalFinishing earliest leaves the most room for whatever comes nextLC 435 · O(n log n)

kept0last end−∞

1def max_non_overlapping(intervals):2    intervals.sort(key=lambda x: x[1])   # by END time — not start3    count, last_end = 0, -inf4    for s, e in intervals:5        if s >= last_end:                # compatible with what we kept6            count += 17            last_end = e8    return count

sortedSorted by **end** time, and that choice is the entire insight. Sorting by start time is the intuitive move and it is wrong: a long interval starting early can block several short ones. Finishing earliest leaves the most room for whatever comes next.

Play‹›1/12⟲

Sorting by start time is the intuitive move and it is wrong: one long interval starting early can block several short ones. The exchange argument for end-time sorting is what makes this greedy provably optimal rather than merely plausible.

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

$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.

Sort by end, not by start

Sorting by start and keeping the first compatible interval is wrong. On [[1, 100], [2, 3], [4, 5]]:

• By start: keep [1,100], then [2,3] and [4,5] both conflict → 1.
• By end: keep [2,3], then [4,5] → 2. Correct.

Sorting by duration is also wrong. On [[1,5],[4,6],[5,9]] the shortest is [4,6], which blocks both [1,5] and [5,9] → 1, where the answer is 2.

Only “earliest finish” is safe.

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 g be the interval finishing earliest overall, and let OPT be any optimal solution.

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

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

This is what “greedy is provably correct” means

An exchange argument shows a greedy choice never costs you anything: any optimal solution can be rewritten to include your choice without getting worse. That is the difference between a greedy algorithm you can defend and a heuristic you are hoping works.

When a greedy approach is wrong, the exchange argument is exactly what fails — try running it on “sort by start” and step 3 collapses, because a long early interval can block intervals that f would have allowed.

Dry run

intervals = [[1,2], [2,3], [3,4], [1,3]]. Sorting by end time reorders them to [1,2] · [2,3] · [1,3] · [3,4] — note [1,3] lands third, after [2,3], because ties on the end value keep their relative order and 3 = 3.

interval	start >= last_end?	decision	last_end	kept
[1,2]	— (seed)	keep	2	1
[2,3]	2 ≥ 2 ✓	keep	3	2
[1,3]	1 ≥ 3 ✗	skip — overlaps what we already committed to	3	2
[3,4]	3 ≥ 3 ✓	keep	4	3

Answer 3, and therefore LC 435’s answer — removals — is 4 − 3 = 1.

• The scan never reconsiders. Once [2,3] is committed, [1,3] is rejected without comparing it against anything else. That is what makes this greedy rather than a DP, and the exchange argument above is what licenses it.
• start >= last_end, not >. Intervals are half-open here: [2,3] may begin exactly where [1,2] ends. If the problem’s intervals are inclusive ([2,3] and [1,2] both occupy point 2, as in some scheduling variants) the test becomes start > last_end. One character, and it only shows up on the touching-intervals test case.
• [1,3] is the interval that punishes sorting by start. Sorted by start it would come second, be kept, and block [2,3] — giving 2 instead of 3. Sorted by end, the earliest-finishing option always wins, which is exactly the property the proof needs.

Complexity

Step	Cost
Sort by end time	$O(n \log n)$ — dominates
Single scan	$O(n)$
Extra space	$O(1)$ beyond the sort (Python’s sort is $O(n)$ auxiliary)
Total	$O(n \log n)$ time

The $O(n \log n)$ is a hard floor for the comparison-based version, and worth saying why: this problem is at least as hard as detecting whether any two intervals overlap, which is element-distinctness-like and $\Omega(n \log n)$ in the comparison model. If the input is already sorted by end time, the whole thing is $O(n)$ — worth asking about, because several LeetCode variants hand you sorted input (LC 57) and the follow-up is often “what if it were already sorted?”

Contrast the alternatives on the same problem:

Approach	Time	Correct?
Sort by end, greedy scan	$O(n \log n)$	✅
Sort by start, greedy scan	$O(n \log n)$	❌ — fails [[1,100],[2,3],[4,5]]
Sort by duration, greedy scan	$O(n \log n)$	❌ — fails [[1,5],[4,6],[5,9]]
DP over intervals (weighted case)	$O(n \log n)$ with binary search	✅ — and required once intervals carry weights

That last row is the boundary: greedy counts how many, but as soon as each interval has a value and you want maximum total value, earliest-finish is no longer optimal and you need the DP (LC 1235).

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_end	len - kept
452 Burst balloons	end	start > last_end	kept (arrows)
646 Longest chain	end	start > last_end	kept
1024 Video stitching	start	(different — interval covering)	jumps

>= versus > is the whole difference between 435 and 452

In 435, intervals are half-open: [1,2] and [2,3] do not overlap, so start >= last_end counts as compatible.

In 452, an arrow at position x bursts any balloon with start <= x <= end — endpoints inclusive. A balloon starting exactly at last_end is still hit by that arrow, so it needs no new arrow, and the condition for needing one is the strict start > last_end.

Get this backwards and [[1,2],[2,3]] gives 2 instead of 1 (LC 452) or 0 instead of… you get the idea. Ask about endpoint conventions.

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^5, -5 * 10^4 <= start < end <= 5 * 10^4.

Examples. [[1,2],[2,3],[3,4],[1,3]] gives 1 (remove [1,3]) · [[1,2],[1,2],[1,2]] gives 2 · [[1,2],[2,3]] gives 0

pch.exerciseTag pch.exerciseTitle

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_kept.

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

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

[[1,2],[2,3]] returning 0 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] on the x-axis. An arrow shot straight up at x bursts every balloon with start <= x <= end. Return the minimum number of arrows needed to burst them all.

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

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

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Sort by end. Shoot the first arrow at 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]] giving 2 is the inclusive-endpoint test. Sorted by end, the first arrow goes at 2, bursting [1,2] and [2,3] (because 2 is inside [2,3]). The next unburst balloon is [3,4], so the second arrow at 4 bursts [3,4] and [4,5]. Two arrows.

Using >= instead of > would demand a new arrow for [2,3] and return 4 — 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.

A note on 32-bit ranges

The constraints allow coordinates spanning the full signed 32-bit range, so in C++ or Java the classic (start + end) / 2 midpoint or a start - end comparator overflows. Python’s integers are arbitrary precision so this is a non-issue here — but sorting by end rather than computing differences is the habit that stays correct in any language.

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 last 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] and left < right, a pair [c, d] can follow [a, b] if b < c. Return the length of the longest chain you can form, choosing and ordering pairs freely.

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

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

pch.exerciseTag pch.exerciseTitle

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

[[1,2],[2,3],[3,4]] giving 2 is the strictness check: [1,2] cannot be followed by [2,3] because 2 < 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 <= 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

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

LC 1024 is a different greedy, despite looking the same

Video Stitching gives you clips and asks for the fewest that cover [0, time] completely. That is covering, not selecting non-overlapping — and overlaps are now desirable rather than forbidden.

So the recipe inverts: sort by start, and among all clips starting within your current reach, take the one extending furthest right. That is the same greedy as Greedy Reachability and Jumps (LC 45), not this page’s. Sorting by end here gives wrong answers.

Two nearly identical-looking problem statements, two different greedies. The question to ask yourself is am I choosing a subset, or covering a range?

8 problems

1 easy7 medium0 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

AllEasyMediumHard

Unsolved onlyExportImportReset

• ○252Meeting RoomspremiumeasyNeetCode 150Blind 75
• ○621Task SchedulermediumNeetCode 150metaamazonuber
• ○435Non-overlapping IntervalsmediumMaximise kept, then subtract; `>=` for half-openNeetCode 150Blind 75
• ○452Minimum Number of Arrows to Burst BalloonsmediumInclusive endpoints, so the comparison is strict `>`LeetCode Top Interview 150
• ○646Maximum Length of Pair ChainmediumStrict chain rule; seed `last` at $-\infty$ for negatives
• ○763Partition LabelsmediumNeetCode 150
• ○846Hand of StraightsmediumNeetCode 150
• ○1024Video Stitchingmedium**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]] breaks sort-by-start; [[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 1 kept / 0 removed / 1 arrow.
• All identical — [[1,2],[1,2],[1,2]]; only one survives.
• Touching endpoints — [[1,2],[2,3]]; the >= vs > test, and it differs by problem.
• One interval swallowing all others — [[1,100],[2,3],[4,5]]; breaks sort-by-start.
• Negative coordinates — seed last at float("-inf"), never 0.
• Already sorted input — no special handling, but a plausible test.
• Empty input — return 0; guard before intervals[0].
• Fully nested intervals — sorting by end naturally prefers the inner one, which is correct.

Self-check

pch.quizTag Greedy interval scheduling — self-check

1. Why sort by END time rather than by start time?

   A Because end times are usually larger and sort faster B Because committing to the earliest-finishing interval leaves the most room for everything after it — sorting by start fails on [[1,100],[2,3],[4,5]], keeping 1 interval where the answer is 2 C Because start times can repeat D Either works; end time is just conventional
   pch.quizShowAnswer

   B — Because committing to the earliest-finishing interval leaves the most room for everything after it — sorting by start fails on [[1,100],[2,3],[4,5]], keeping 1 interval where the answer is 2 — The exchange argument makes it precise: any optimal solution can be rewritten to start with the earliest-finishing interval without getting worse, so the greedy choice is always safe.

2. Is sorting by shortest duration a valid alternative?

   A Yes, shortest-first is equivalent B No — on [[1,5],[4,6],[5,9]] the shortest is [4,6], which blocks both [1,5] and [5,9] for a total of 1, where the answer is 2 C Yes, but only when no intervals overlap D Yes, and it is faster
   pch.quizShowAnswer

   B — No — on [[1,5],[4,6],[5,9]] the shortest is [4,6], which blocks both [1,5] and [5,9] for a total of 1, where the answer is 2 — Shortest-first is the most plausible-sounding wrong answer, so it is worth carrying the counterexample. Only earliest-finish is safe.

3. The compatibility test is `start >= last_end`. When would it be `start > last_end`?

   A Never B When intervals are inclusive on both ends — if [1,2] and [2,3] both occupy point 2 they conflict, whereas half-open intervals do not C When the input is unsorted D When intervals can have zero length
   pch.quizShowAnswer

   B — When intervals are inclusive on both ends — if [1,2] and [2,3] both occupy point 2 they conflict, whereas half-open intervals do not — One character, and it only shows up on the touching-intervals test case — the same half-open-versus-inclusive decision that drives the sweep-line tie-break.

4. LC 435 asks for the minimum number of intervals to ERASE. How does that relate to this template?

   A It needs a different algorithm B It is the same computation: erasures = n − (maximum number of non-overlapping intervals kept) C Sort by start instead D Count overlapping pairs
   pch.quizShowAnswer

   B — It is the same computation: erasures = n − (maximum number of non-overlapping intervals kept) — In the dry run, 4 intervals with 3 kept means 1 erasure. Recognising the complement is often the whole insight a problem is testing.

5. Each interval now carries a value, and you want the maximum total value of a non-overlapping subset. Does the greedy still work?

   A Yes, sort by value descending B No — earliest-finish is no longer optimal once intervals are weighted; that is weighted interval scheduling, solved by DP with binary search in O(n log n) (LC 1235) C Yes, unchanged D Yes, sort by value divided by duration
   pch.quizShowAnswer

   B — No — earliest-finish is no longer optimal once intervals are weighted; that is weighted interval scheduling, solved by DP with binary search in O(n log n) (LC 1235) — This is the boundary of the pattern. A single high-value long interval can beat many cheap short ones, which no ordering-based greedy can see.

6. What is the complexity, and what would make it faster?

   A O(n) always B O(n log n), dominated by the sort — and O(n) if the input arrives already sorted by end time, which some variants guarantee C O(n²) because of the compatibility checks D O(n log n) with no possible improvement
   pch.quizShowAnswer

   B — O(n log n), dominated by the sort — and O(n) if the input arrives already sorted by end time, which some variants guarantee — The scan itself is one pass with O(1) state. Asking whether the input is pre-sorted is a cheap question that occasionally changes the answer you can offer.

Recall card

• Cue — “maximum number of non-overlapping intervals”, “minimum removals”, “can one resource serve all of these”; unweighted.
• Do — sort by end time, then scan keeping any interval whose start >= last_end, updating last_end on each keep.
• Why end time — earliest finish leaves the most room; the exchange argument turns that intuition into a proof.
• Wrong sort keys — by start fails [[1,100],[2,3],[4,5]]; by duration fails [[1,5],[4,6],[5,9]]. Carry both counterexamples.
• >= vs > — half-open intervals may touch; inclusive ones may not.
• Erasures = n − kept (LC 435).
• Cost — $O(n \log n)$ from the sort, $O(n)$ scan, $O(1)$ state. $O(n)$ if pre-sorted.
• Boundary — weighted intervals break the greedy entirely: that is DP + binary search (LC 1235). Counting overlaps rather than selecting is the sweep line.

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 - 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.