cf.completefrontend
GREEDY & INTERVALS · CORE

Interval scheduling (earliest end first)

Pick the most time ranges that don't overlap by always taking the one that ends first.

Time O(n log n)Space O(n)6 practice problemsStep-through picture

The idea

An interval is a range with a start and an end, like a meeting from 9:00 to 10:30, written [start, end]. Two intervals overlap when they share some time. Interval scheduling asks: from a pile of intervals, how many can you keep so that no two overlap?

The greedy rule is to sort the intervals by their end time and walk through them. Keep an interval if it starts at or after the end of the last one you kept, and skip it otherwise. Taking the interval that ends first leaves as much time as possible for everything after it.

This also answers the opposite question: the fewest intervals to remove so the rest don't overlap is the total minus the number kept. And with a small change it answers "the fewest points that hit every interval", like the fewest clicks that pop every balloon on a timeline.

An everyday example

Seeing as many talks as you can at a conference

A conference has many talks in one day, and you can only sit in one room at a time. You want to see as many talks as you can, whatever they're about. The trick is to pick the talk that finishes earliest, because it frees you up soonest. Then pick the earliest-finishing talk that starts after that one ends, and so on.

How the example maps to the code
In the exampleIn the code
Listing the talks by finish timesorted by a[1] - b[1]
When your last chosen talk endslastEnd
The next talk starts after you're freestart >= lastEnd
Going to itcount++; lastEnd = end
The talks you can seecount

From the slow way to interval scheduling (earliest end first)

  1. The obvious way is to try every subset of the intervals, check that no two in it overlap, and keep the biggest subset. With n intervals that is 2^n subsets, and each one needs its own overlap check. Twenty meetings already give over a million subsets.
  2. Think about the first interval in a best answer, the one that happens earliest. What does it mean for the rest of the schedule? Only its end matters: everything after it must start at or after that end. So a first pick that ends earlier leaves more room for the rest, never less.
  3. That suggests a rule: of all intervals, pick the one that ends first. It may not start first and it may not be the shortest, but it frees the timeline soonest. After picking it, throw away every interval that starts before its end. What's left is the same problem, only smaller.
  4. Repeating that rule is easy if the intervals are sorted by end time once. Walk them in that order and remember lastEnd, the end of the last interval you kept. Keep the next interval only if it starts at or after lastEnd. That loop is interval scheduling by earliest end.

How it works

  1. Sort the intervals by end time, earliest end first.
  2. Set lastEnd to -Infinity, so the first interval can always be kept, and count to 0.
  3. For each interval [start, end] in sorted order, check if it starts at or after lastEnd.
  4. If it does, keep it: add one to count and set lastEnd = end.
  5. If it doesn't, it overlaps the last kept interval, so skip it.
  6. After the loop, count is the most intervals that don't overlap.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function maxNonOverlapping(intervals) {
  2. const sorted = [...intervals].sort((a, b) => a[1] - b[1]);
  3. let count = 0;
  4. let lastEnd = -Infinity;
  5. for (const [start, end] of sorted) {
  6. if (start >= lastEnd) {
  7. count++;
  8. lastEnd = end;
  9. }
  10. }
  11. return count;
  12. }

How fast it is

TimeO(n log n)
Extra memoryO(n)

Sorting dominates. The loop is one pass with constant work per interval. The sorted copy uses O(n) memory.

  • Best caseO(n)

    The intervals are already sorted by end. V8's TimSort notices that in one pass, and the loop is one more pass.

  • Average caseO(n log n)

    Intervals in random order: the sort costs O(n log n) and the loop adds O(n).

  • Worst caseO(n log n)

    Any order that isn't close to sorted. The loop is always exactly n steps, however many intervals are kept, so the sort decides the cost.

Common mistakes

  • Sorting by start time. One long interval that starts early gets kept and blocks many short ones.
  • Sorting by length. A short interval can sit across two others that would both fit without it.
  • Mixing up >= and > for touching intervals, so [1, 3] and [3, 5] are treated the wrong way for the problem.
  • Using it when intervals have different values or weights. Then the most intervals isn't the best total, and you need dynamic programming with binary search.

When to use it

Look for these clues in a problem:

  • The input is a list of time ranges or [start, end] pairs.
  • The question asks for the most ranges that don't overlap, or the fewest to remove so none overlap.
  • It asks for the fewest points (arrows, clicks, checks) that touch every range.
  • Every range is worth the same. If ranges have different values, you need dynamic programming instead.

Check yourself

Answer each one in your head first, then open it.

Why does picking the shortest interval first fail?

A short interval can sit across two longer ones that don't overlap each other. For [1, 5], [4, 7], [6, 10], shortest-first keeps [4, 7] and must skip both others, so it gets 1 instead of 2.

Why does lastEnd start at -Infinity and not 0?

So the first interval is always kept, even if it has negative times. With 0, an interval like [-3, -1] would be skipped.

If the loop keeps count intervals out of n, how many must be removed so none overlap?

n - count. Keeping the most intervals is the same as removing the fewest.

How many times does the test start >= lastEnd run for n intervals?

Exactly n times, once per interval, no matter how many are kept. The sort before the loop costs more than that.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 6 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The rule the loop keeps: the intervals kept so far don't overlap, and no other non-overlapping choice from the intervals seen so far has more intervals, or the same number with a smaller lastEnd. A smaller lastEnd is never worse, because it lets more later intervals in. The rule is true at the start, with nothing kept and lastEnd = -Infinity.

The exchange argument shows why. Take any best answer and line its intervals up in time order. Greedy's first pick ends no later than the best answer's first interval, because greedy took the earliest end of all. Swap the best answer's first interval for greedy's: nothing after it can overlap now, since the new one ends even earlier. Then do the same for the second interval, among those that start at or after the first end, and so on.

After all the swaps, the best answer starts with exactly greedy's picks. It can't have any extra interval after them: an extra one would start at or after greedy's final lastEnd, and greedy would have kept it when the loop passed it. So greedy's count equals the best count. The loop ends because it visits each of the n sorted intervals exactly once.

Going deeper

3 more ideas

Why the earliest end is always a safe first pick

Take any best answer and look at its first interval. Swap it for the interval that ends earliest overall. The swapped-in interval ends no later, so it can't overlap anything that came after the old first interval. The answer has the same size and still has no overlaps. Repeating this argument for each next pick shows the greedy answer is as large as any best answer.

Touching ends: >= or >

Whether [1, 4] and [4, 6] overlap depends on the problem. For meetings, one can start the moment the other ends, so they don't overlap: use start >= lastEnd. For closed ranges where both ends count, like balloons that are popped by an arrow at either edge, touching means overlapping: use start > lastEnd. Read the statement carefully.

Why it takes O(n log n) time

Sorting by end time costs O(n log n). The loop looks at each interval once and does constant work. Sorting by start time is a common mistake: a very long interval that starts first would be kept and block many short ones.

Work it by hand

Every step in a table, with why

Keep the most intervals with no overlap. The longest interval starts first, and three kept intervals touch end to start.

intervals = [[2, 6], [1, 3], [3, 4], [5, 8], [4, 7], [0, 9], [7, 10], [8, 11]]

Step[start, end]start >= lastEndlastEndcountWhat happensWhy
1---Infinity0sort by endSorted by end: [1, 3], [3, 4], [2, 6], [4, 7], [5, 8], [0, 9], [7, 10], [8, 11]. Nothing is kept yet.
2[1, 3]1 >= -Infinity31keepThe first interval always passes, because lastEnd starts at -Infinity.
3[3, 4]3 >= 342keepIt starts exactly when [1, 3] ends. With >=, touching intervals don't overlap, so it is kept.
4[2, 6]2 >= 4 is false42skipIt starts at 2, while [3, 4] is still running.
5[4, 7]4 >= 473keepAnother touching pair: it starts the moment [3, 4] ends.
6[5, 8]5 >= 7 is false73skipIt starts inside [4, 7].
7[0, 9]0 >= 7 is false73skipThe longest interval starts first of all. Sorting by start would keep it first, and then every other interval would overlap it, for a count of 1.
8[7, 10]7 >= 7104keepIt starts exactly when [4, 7] ends.
9[8, 11]8 >= 10 is false104skipThe last interval overlaps [7, 10]. Every interval has been seen, so the loop ends.

It returns 4: [1, 3], [3, 4], [4, 7], and [7, 10]. A brute force over all 256 subsets agrees that 4 is the most. Removing the other 4 intervals is the fewest removals that leave no overlap.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Interval scheduling (earliest end first)O(n log n)O(n)You want the most intervals with no overlap, and every interval is worth the same.
Sort by start, keep the earlier end on overlapO(n log n)O(n)The intervals are already sorted by start. On each overlap, keep whichever of the two ends first; the count comes out the same.
Weighted DP with binary searchO(n log n)O(n)Intervals have different values and you want the most total value, not the most intervals.
Try every subsetO(2^n)O(n)Only to check the greedy answer on tiny random tests.

Extra memory: O(n) for the sorted copy. The loop itself uses two numbers, count and lastEnd.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Interval scheduling (earliest end first) and the other approaches, on a scale where each line up is 10 times more steps.
  • Interval scheduling (earliest end first), Sort by start, keep the earlier end on overlap, Weighted DP with binary search O(n log n)
  • Try every subset O(2^n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Interval scheduling (earliest end first)339,96620 million
Sort by start, keep the earlier end on overlap339,96620 million
Weighted DP with binary search339,96620 million
Try every subset1,024more than a quadrillionmore than a quadrillion

Inputs that need care

5 tricky inputs
No intervals: []
The loop never runs and it returns 0.
Touching intervals: [[1, 4], [4, 6]]
4 >= 4 is true, so both are kept and it returns 2. If touching ends count as shared time, change the test to start > lastEnd, and it returns 1.
Identical intervals: [[2, 5], [2, 5], [2, 5]]
After the first is kept, lastEnd is 5 and each copy fails 2 >= 5, so it returns 1.
A zero-length interval with a tied end: [[3, 3], [1, 3], [3, 6]]
Sorted by end only, [3, 3] stays before [1, 3]. Keeping it sets lastEnd = 3, so [1, 3] is skipped and it returns 2, but all 3 fit. Break end ties by start, a[1] - b[1] || a[0] - b[0], and it returns 3.
Negative times: [[-3, -1]]
Because lastEnd starts at -Infinity, the interval is kept and it returns 1. Starting lastEnd at 0 would wrongly skip it.

Variations and follow-ups

Twists interviewers add

Fewest intervals to remove

The fewest removals so the rest don't overlap is intervals.length - count. It is the same loop; only the question is turned around.

Fewest points that hit every interval

Sort by end and put a point at the end of the first interval. Every interval that starts at or before that point contains it. Put the next point at the end of the first interval that starts after it. This is the same loop with start > lastEnd, because a point on an edge hits both intervals.

Weighted intervals

If each interval has a value and you want the most total value, earliest end can lose: one long, valuable interval may be worth more than three short ones. Sort by end and use dynamic programming: best[i] is the larger of skipping interval i, or taking it plus the best answer for the intervals that end before it starts, found by binary search. That is O(n log n).

Fewest rooms for every interval

If every interval must be kept and you want the fewest rooms, it's a different question. The answer is the most intervals that overlap at one moment, found with a sweep line or a min-heap of end times.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "the most meetings one person can attend", "the fewest intervals to remove so the rest don't overlap", or "the fewest arrows or points that hit every range". All three are this loop with a small change.
  • Say why end time and not start time: "the interval that ends first leaves the most room for everything after it". Then give the counterexample for start time: one long interval that starts first blocks all the short ones.
  • Ask whether touching intervals overlap before writing the comparison. It decides >= versus >, and it's the most common place to lose points.
  • Test by hand: an empty list, identical intervals, and a chain of touching intervals like [1, 2], [2, 3], [3, 4]. The usual follow-up is "what if intervals have weights?": answer with sorting by end plus dynamic programming and binary search.

Where frontend code uses it

The same idea in real UI code
  • A calendar widget that suggests the most meetings a person can attend from a list of invites.
  • Deciding which toast notifications or banners to show when each one has a time window and only one can be visible at a time.
  • Picking the most ad slots or promo banners in a video timeline that don't overlap.

Related algorithms