Intervals

1The mental model (what this really is)#

An interval is just a pair: a start and an end. [2, 5] means "something is busy from 2 to 5."

• Meetings on a calendar.
• A booking on a hotel room.
• A range of IP addresses.
• The numbers can be times, positions, byte offsets, anything ordered along one axis.

Almost every interval problem reduces to one question: how do two intervals relate on a number line?

• Two intervals either overlap or they do not. That is it.
• Answer that cleanly and the rest is plumbing.

The single fact that unlocks most of these. Two intervals A and B overlap when:

A.start <= B.end AND B.start <= A.end

• Say it out loud a few times: neither one starts after the other one ends.
• If you remember nothing else, remember this.
• The negation is just as useful: they are disjoint when A.end < B.start OR B.end < A.start, which is the "there is a gap" case.

The second big idea: sorting turns chaos into a line you can sweep.

• Random order means you cannot reason about neighbors, so the naive approach compares every pair: O(n^2), about 100 million comparisons for 10,000 intervals.
• Sort by start and each interval only needs comparing against the one next to it.
• That one move drops you to O(n log n), roughly 10,000 * 14, about 140,000 operations for the same input.
• Same answer, three orders of magnitude cheaper.

2How to recognize it (the signals in a problem)#

Train your ear for these phrases. When you hear them, your hand should already be reaching for "sort by start."

• "Merge overlapping..." anything.
• "Can this person attend all meetings?" or "How many rooms do we need?"
• "Insert a new interval and keep the list tidy."
• "Find the minimum number of X to cover / remove / cover all gaps."
• The input is literally a list of pairs [[1,3],[2,6],...].
• Anything about free time, conflicts, double booking, ranges, or coverage.

One more tell, and it is a trap. If the problem counts how many things are active at the same time (max concurrent meetings, max planes in the air, peak traffic), that is a different animal.

• You do not merge there. You sweep events.
• Candidates reach for the merge template, get a clean merged list, then realize it answers the wrong question.
• It is covered under variations below, because this is exactly where people trip.

3The template (how it works, with pseudocode)#

Ninety percent of interval problems start the exact same way. Burn this into muscle memory.

• Step 1. Sort by start. (Sometimes by end, flagged later.)
• Step 2. Walk the sorted list, keeping the "current" interval you are building or comparing against.
• Step 3. For each next interval, ask: does it overlap the current one? Yes means do something (merge, count, reject). No means close out the current one and move on.

Here is the canonical merge template:

function merge(intervals):
    if intervals is empty: return []

    sort intervals by start ascending

    result = [ intervals[0] ]        # seed with the first one

    for each iv in intervals[1:]:
        last = result[-1]            # the interval we're currently extending

        if iv.start <= last.end:             # they overlap (or touch)
            last.end = max(last.end, iv.end) # swallow it
        else:
            result.append(iv)                # gap: start a fresh interval

    return result

Why the overlap check shrank to iv.start <= last.end.

• Sorting already guarantees last.start <= iv.start, so the other half of the two-sided condition is free.
• That is the payoff of sorting: you never compare backward.

Why max(last.end, iv.end) and not just iv.end.

• Take [1, 10] then [2, 3]. The second is fully inside the first.
• Blindly take iv.end and you shrink to [1, 3], losing coverage from 3 to 10.
• Always take the max. This exact slip fails otherwise-correct solutions on the hidden "nested interval" test case.

Here is the shape of the walk, so you can see why it stays one pass:

4A worked example (walk through one problem step by step)#

The classic: Merge Intervals. Given [[1,3], [2,6], [8,10], [15,18]], return the list with all overlaps merged.

• Sort by start. Already sorted here: [1,3], [2,6], [8,10], [15,18]. Do not skip this in your head just because it looks sorted. Say "first I sort by start, O(n log n)." It signals you know the pattern and protects you when the grader hands you an unsorted input on the next run.
• Seed the result with the first interval. result = [[1,3]]. The interval you are holding open is [1,3].
• Next: [2,6]. Is 2 <= 3? Yes, they overlap. Merge: new end is max(3, 6) = 6. Held interval becomes [1,6]. result = [[1,6]]. Narrate this one: the 2 falls inside [1,3], the ranges touch, and together they cover 1 all the way to 6. One continuous block.
• Next: [8,10]. Is 8 <= 6? No. 8 is past where the current block ends, so there is a gap between 6 and 8. Close out [1,6] for good and start holding [8,10]. result = [[1,6], [8,10]].
• Next: [15,18]. Is 15 <= 10? No. Another gap. Close [8,10], start holding [15,18]. result = [[1,6], [8,10], [15,18]].

Done. Final answer: [[1,6], [8,10], [15,18]].

• Walk it once on paper and you feel the "current held interval" idea do all the work.
• You never look backward: you only compare the new interval against the last thing in your result.
• That is why it is linear after the sort: n comparisons, n appends at most, no nested loop anywhere.

5Variations and gotchas#

The merge template is the base. Here are the mutations interviewers throw at you.

Insert Interval (list already sorted).

• Given a sorted, non-overlapping list and one new interval.
• Three phases: add all intervals that end before the new one starts, merge everything that overlaps the new one into it, then add all intervals that start after the new one ends.
• O(n), no sorting needed since the input is pre-sorted.
• The trap is phase two: keep absorbing while interval.start <= new.end, taking the min of starts and the max of ends, before you push the one merged block.

Can attend all meetings?

• Sort by start.
• If any meeting starts before the previous one ended (curr.start < prev.end), return false.
• One pass, O(n log n) for the sort, O(1) extra space.

Meeting Rooms II (minimum rooms). This is the "max concurrent" family, and it does not use the merge template. Two clean approaches:

1. Two sorted arrays. Pull out all start times and all end times, sort each. Walk a pointer through starts. Every time a meeting starts before the earliest unmatched end, you need a new room. Otherwise free a room by advancing the end pointer.

2. Min-heap of end times. Sort by start. For each meeting, if the heap's smallest end time is <= current start, pop it (reuse that room). Push the current end. The heap size at its peak is your answer.

3. Both are O(n log n).

4. The heap version generalizes nicely: swap the heap for a counter and you have the line sweep below, swap it for a sum and you have Car Pooling.

Event sweep / line sweep (max people in the room at once).

• Turn each interval into two events: (start, +1) and (end, -1).
• Sort all events, sweep left to right, keep a running counter, track the max.
• Watch the tie-break: if a meeting ends at the same time another starts, do they share a room? Usually an end at the same instant frees the room first, so process -1 before +1 at equal timestamps.
• Ask the interviewer about this edge. It shows maturity, and it is the difference between an answer of 2 and an answer of 1 on the boundary case.

Sort by END instead of start. The one people miss.

• For "maximum number of non-overlapping intervals you can keep" (interval scheduling / "erase overlap"), sort by end time and greedily keep whatever finishes earliest.
• Finishing early leaves the most room for others.
• Sorting by start here gives wrong answers on inputs like [[1,100],[2,3],[3,4]], where keeping the long early-starting interval blocks two short ones.
• Know both keys and know why.

Closed vs open, touching endpoints.

• Is [1,2] and [2,3] an overlap or not? Depends on the problem.
• For merging, touching usually counts (<=), so they fuse into [1,3].
• For "attend all meetings," a meeting ending exactly when the next starts is usually fine (<).
• Clarify this out loud. It is a real source of off-by-one bugs and a free place to show you think about boundaries.

6Complexity#

For the whole merge / attend-meetings / insert family:

• Time: O(n log n), dominated by the sort. The sweep after it is O(n).
• Space: O(n) for the output list, or O(log n) to O(n) for the sort's internal memory depending on the language (Python's Timsort is O(n), a typical in-place quicksort is O(log n)). If asked to merge in place, you can sometimes get O(1) extra, but the output usually forces O(n).

For the heap-based room-counting:

• O(n log n) time.
• O(n) space for the heap in the worst case (every meeting overlaps, so the heap holds all n ends at once).

The one exception: Insert Interval into an already-sorted list is O(n), because you skip the sort.

• Catch that the input is pre-sorted and still sort it, and you have left the better answer on the table, dropping from O(n) to O(n log n) for no reason.
• Interviewers notice. This is the single most common way a candidate turns a strong answer into an average one on this problem.

7Mistakes that cost people the round#

These sink candidates who clearly knew the idea.

• Forgetting max(last.end, iv.end). The fully-nested case ([1,10] then [2,3]) silently breaks and you lose coverage. The number one bug.
• Using < when you need <= for touching intervals, or the reverse. Settle it with the interviewer before you code. Guessing costs a test case and the look of carelessness.
• Sorting by the wrong key. Merge and attend-meetings: sort by start. Maximum non-overlapping set: sort by end. Mix these up and your logic is right but your answer is wrong, the worst way to fail because the code reads as correct.
• Trying to merge for a "max concurrent rooms" problem. Merging tells you coverage, not concurrency. Different question, different tool (heap or sweep).
• Mutating the input list while iterating it. Build a fresh result. Do not delete from the array you are looping over, and watch that merging in place does not alias the caller's objects.
• Not handling empty input. One line at the top. Free points, and it shows you test your own code.
• Over-nesting conditionals. The clean solution has one overlap check and an else. Four nested ifs means you have lost the thread. Step back and re-derive from the single overlap rule.

Right logic with the wrong sort key is the worst failure: the code reads as correct and the answer is still wrong.

8Your practice path (named problems by difficulty)#

Do them in this order. Each one adds exactly one new idea.

Warm up (Easy):

• Merge Sorted Array (gets you comfortable with two sorted sequences)
• Meeting Rooms (the yes/no "can attend all" version)
• Summary Ranges

Core (Medium), do every one of these:

• Merge Intervals (the template, nail it blindfolded)
• Insert Interval (the three-phase trick, spot the pre-sorted input)
• Non-overlapping Intervals (sort by end, greedy)
• Meeting Rooms II (min heap / sweep, max concurrency)
• Interval List Intersections (two-pointer over two sorted lists)
• Minimum Number of Arrows to Burst Balloons (greedy, sort by end)
• Car Pooling (event sweep with a running sum)
• My Calendar I (overlap check on inserts)

Stretch (Hard):

• Employee Free Time (merge across many lists, then find gaps)
• My Calendar II / III (overlap counting with a sweep)
• Data Stream as Disjoint Intervals (maintain merged intervals live)

The four that mean you are ready.

• If you can do Merge Intervals, Insert Interval, Non-overlapping Intervals, and Meeting Rooms II without looking anything up, you are ready for almost any interval question.
• Those four cover the three keys (sort by start, sort by end, and the heap/sweep concurrency tool), and everything else is a remix of them.

Want to see which companies lean on intervals and how they phrase them? Check the company guides to match this pattern to the rooms you'll actually sit in.