Merge Intervals: The Pattern for Overlaps, Bookings, and Timelines

TL;DR: Every interval problem is really two questions: do these overlap? and what do I do when they do? The overlap test is one comparison (a.start <= b.end and b.start <= a.end), and nearly every problem in the family runs the same template: sort by start time, sweep left to right, compare each interval with the last one you kept. Learn the template, learn the two-line overlap test, decide up front how to treat touching intervals, and a family that spans Merge Intervals, Insert Interval, Meeting Rooms, and calendar problems becomes one pattern with costumes.

This is the fourth deep dive in our pattern series, after sliding window, two pointers, and fast & slow pointers. Merge intervals is the most tangible pattern of the four: it's calendar conflicts, meeting room bookings, CPU task scheduling, and hotel reservations. Interviewers love it for exactly that reason, because it dresses up naturally in real-product language ("given a user's meetings...", "given ad slots...") and quietly tests whether you can reason about ordering and edge cases under time pressure.

The tell: how to recognize an interval problem

You should suspect merge intervals the moment the input is pairs with a start and an end, plus any of these words in the problem statement:

• "merge all overlapping intervals"
• "do any meetings conflict?" / "can this person attend all meetings?"
• "insert a new booking into a schedule"
• "minimum number of rooms / resources needed"
• "find the free time / gaps"

The costume changes (meetings, flights, IP ranges, ad slots, temperature readings), but if the data is [start, end] pairs, you're in interval land. And one interview-saving observation: interval problems are rarely algorithmically deep. The algorithm is usually "sort, then one pass." What they actually test is edge-case discipline, and that's a learnable checklist, not a talent.

The two ideas that power everything

1. The overlap test. Two intervals a and b overlap if and only if each one starts before the other ends:

def overlaps(a, b):
    return a.start <= b.end and b.start <= a.end

Don't enumerate cases in the interview ("a could start inside b, or b could start inside a, or..."). There are technically six ways two intervals can relate, and candidates who try to case-match all six write buggy branches. The single test above covers all of them, and knowing that is the pattern.

2. Sorting kills half the cases. After you sort by start time, you never have to ask "does the new interval start before the one I'm holding?" again; it can't. Overlap checking against the last kept interval collapses to one comparison: current.start <= last.end. That's why virtually every solution in this family begins with intervals.sort(key=lambda x: x[0]), and why forgetting to sort is the pattern's most fatal bug.

The template: sort, sweep, merge

def merge(intervals):                      # LeetCode 56
    intervals.sort(key=lambda x: x[0])     # sort by start
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:         # overlaps the last kept one
            merged[-1][1] = max(merged[-1][1], end)   # extend
        else:
            merged.append([start, end])    # gap: start a new interval
    return merged

Three things worth saying out loud in an interview, because each is a graded signal:

• Why max() on the end: a later interval can be swallowed entirely by an earlier one ([1,10], [2,3]), so you extend to the larger end, not simply the new one. This is the bug interviewers wait for.
• Why sorting is the cost: the sweep is O(n), so sorting's O(n log n) dominates. If the input arrives pre-sorted (it often does in follow-ups), the whole thing is linear.
• The touching-intervals decision: do [1,4] and [4,5] overlap? For merging, usually yes (<=). For "can I attend both meetings," a meeting ending at 4 and one starting at 4 usually don't conflict (<). Ask, decide, and state your choice before coding. Half of all interval bugs are this one comparison operator.

The variations, and what each one adds

• Meeting Rooms ("can one person attend all meetings?"): sort, sweep, and the moment current.start < last.end, return false. The template minus the merging.
• Insert Interval (LeetCode 57): the list is already sorted, so don't re-sort. Three phases: append everything that ends before the new interval starts, merge everything that overlaps it (extend the new interval's ends), append the rest. The classic bug is forgetting to add the merged interval itself when the loop ends.
• Interval List Intersections (LeetCode 986): two sorted lists, one pointer each, advance whichever interval ends first. If that sounds familiar, it's the two-sequence template from two pointers wearing an interval costume; patterns compose.
• Meeting Rooms II ("minimum rooms needed"): the family's most-asked question. Sort by start, then track when rooms free up with a min-heap of end times: if the earliest-ending meeting is done before the current one starts, reuse that room; otherwise open a new one. The heap's size at the end (or its max during the sweep) is the answer. This is also where interval problems shake hands with the Top-K/heap pattern.
• Non-overlapping Intervals (LeetCode 435, "remove the fewest intervals to make the rest disjoint"): same sweep, but when two intervals collide you keep the one that ends earlier, a greedy exchange argument, which is the interval family's bridge into greedy algorithms.
• Employee Free Time: merge everyone's schedules into one list, run the standard merge, and the gaps between merged intervals are the answer. A nice reminder that sometimes the output you want is the negative space.

Want every variation taught step by step? The merge intervals chapter of Grokking the Coding Interview works through this whole family with visual timelines and code in six languages, then does the same for all 42 patterns (32 common + 10 advanced).

The three mistakes that sink candidates

1. Sweeping without sorting (or sorting by the wrong key). The one-comparison overlap check is only valid on start-sorted input. Sorting by end time has its place (the greedy variants like Non-overlapping Intervals), which is exactly why candidates half-remember "sort by end" and apply it to plain merging, where it breaks. Default to start; switch to end only when you can say why (you're greedily keeping early finishers).

2. The <= vs < blunder. Touching intervals: merged or not? Conflicting or not? It depends on the problem's semantics, the statement usually tells you, and if it doesn't, asking is a plus-signal. Pick the operator deliberately and test [1,4],[4,5] explicitly before you declare done.

3. Forgetting the swallow case. [1,10], [2,3]: if your merge writes end = new_end instead of end = max(ends), the result shrinks to [1,3] and silently drops [3,10]. Interviewers feed this exact input on purpose. One max() is the difference.

Practice ladder

In order; each rung adds one wrinkle.

1. Meeting Rooms (E): the overlap test plus a sort, nothing else.
2. Merge Intervals (M): the full template; the family's canonical problem.
3. Insert Interval (M): three-phase sweep, no re-sort, watch the final append.
4. Interval List Intersections (M): two lists, two pointers.
5. Meeting Rooms II (M): add the min-heap of end times; the most common interview form.
6. Non-overlapping Intervals (M): the greedy pivot (keep the earlier end).
7. Stretch goal: Employee Free Time (H): k schedules, merged, inverted.

Then write the tell in your own words ("I should suspect merge intervals when ___") and move on, the same drill as every entry in this series, because recognition, not volume, is the skill that passes interviews.

The takeaway

Interval problems are one overlap test, one sort, and one sweep, wrapped in a dozen product costumes. The algorithm is the easy 20%; the graded 80% is discipline: sort by the right key, choose <= or < on purpose, take the max() of ends, and test the touching and swallowed cases before you say done. Master that checklist and this family becomes the most predictable part of any loop. Next in the series: Monotonic Stack, the pattern that barely existed in interviews a decade ago and is now everywhere.

Go deeper: Grokking the Coding Interview teaches all 42 patterns (32 common + 10 advanced) across 300+ sequenced problems, for a one-time $79. Short on time? Grokking 75 covers the essential intervals problems inside a 6-week plan.

FAQs

How do I check if two intervals overlap? One test: a.start <= b.end and b.start <= a.end. It covers all six geometric arrangements of two intervals, so never branch on cases. If the problem treats touching endpoints as non-overlapping (a meeting ending at 4 and another starting at 4), switch both comparisons to strict <.

Why do interval problems always start with sorting? Sorting by start time guarantees that each new interval can only overlap the most recent one you've kept, never anything earlier, which turns overlap detection into a single comparison per interval. Without the sort you'd have to compare every pair, which is O(n²).

When do I sort by end time instead of start time? When you're greedily selecting intervals rather than merging them: problems like Non-overlapping Intervals or maximum-meetings-in-one-room keep the interval that ends earliest because it leaves the most space for the rest. Merging and conflict detection sort by start; greedy selection sorts by end.

How does Meeting Rooms II actually work? Sort meetings by start. Keep a min-heap of end times for occupied rooms. For each meeting, if the smallest end time is at or before the meeting's start, pop it (that room frees up); then push the new end time. The heap's maximum size during the sweep is the minimum number of rooms.

Are interval questions common in FAANG interviews? Very. Merge Intervals and Meeting Rooms II are perennial at Meta, Google, and Amazon precisely because they map to real product scheduling and expose edge-case discipline fast. They're rarely the hardest question in a loop, but they're one of the most commonly failed easy-mediums, almost always on the sort key, the touching-endpoints operator, or the swallow case.