← Learn DSA · Lesson 10 of 11

Intervals

Sort by the right endpoint, then sweep — almost every interval problem.

The idea

Interval problems are a small family with a shared opening move: sort, then sweep. What you sort by decides which problem you are solving, and getting that wrong is the most common failure here.

Sort by start for merging. Walk the list holding the current merged interval; if the next one begins before the current one ends, extend the end. Otherwise emit and start fresh.

Sort by end for scheduling. To keep as many non-overlapping intervals as possible, repeatedly take the one that finishes earliest — it leaves the most room for whatever comes next. Sorting by start, or by duration, gives a plausible algorithm with wrong answers.

Split into events for anything about simultaneity. Turn each interval into a +1 at its start and a -1 at its end, sort all the events by time, and sweep: the running total is how many intervals are active. That is the meeting rooms problem, and it generalises to any "how many at once" question.

Two overlap tests worth memorising, because getting them backwards produces off-by-one bugs that survive testing:

overlap:     a.start < b.end && b.start < a.end
no overlap:  a.end <= b.start || b.end <= a.start

Whether touching endpoints count as overlapping is a question to ask, not to assume — [1, 2] and [2, 3] are adjacent for meeting rooms and overlapping for some other problems.

Walkthrough

Intervals stored flat as start, end, start, end — already sorted by end time. Each pair is kept only if it begins after the last one finished.

What it costs

time
O(n log n), all of it the sort — the sweep itself is O(n)
space
O(1) beyond the sort, or O(n) if you build an event list

Once the input is already sorted, every problem in this family drops to a single linear pass. It is worth checking the constraints for that, because it is often stated.

When to reach for it

Rather than the obvious alternative

A nested loop comparing every pair

O(n²) and the obvious first idea. Sorting removes the need to compare anything but neighbours, which is the entire gain.

A min-heap of end times

The right tool for meeting rooms if you want the rooms themselves rather than just a count — the heap holds each active interval. The sweep is cheaper when only the maximum count is asked for.

A segment tree

Needed when intervals are inserted and removed between queries. For a fixed set processed once, it is far more machinery than the problem requires.

How to spot it

Where it goes wrong

Sorting by start when the problem needs end

Merging sorts by start; maximising non-overlapping count sorts by end. The two are one character apart in code and give different answers.

Guessing about touching endpoints

Whether `[1, 2]` and `[2, 3]` overlap is a property of the problem, not of intervals. Ask, or state your assumption explicitly.

Extending with the wrong end

When merging, the new end is `max(current.end, next.end)` — not `next.end`. An interval fully contained in the current one would otherwise shrink it.

Try it

Two short checks. They run the same way the practice problems do — write the function, press Run.

Given intervals flat as [s, e, s, e, ...] sorted by start, return true if any two overlap.

Or press ⌘↩

Tests

4 cases, 1 hidden
calltypeexpectedresult
anyOverlap([1,4,2,5])overlappingtrue—
anyOverlap([1,2,3,4])disjointfalse—
anyOverlap([1,2,2,3])touching endpointsfalse—
withheldhiddenwithheld—

Hidden cases run too — their inputs aren't listed here, so aim for a general solution rather than one fitted to the cases above.

Hints

Stuck? Hints open one at a time, each giving a little more away.

2 hints left

Practise it