The Merge Intervals Pattern for Coding Interviews

The merge intervals pattern handles any problem framed as a set of ranges — meetings, bookings, time slots, numeric spans. Once you sort the intervals by start time, a single left-to-right pass answers most questions about how those ranges overlap. It is one of the highest-frequency shapes in interviews, and it almost always turns an O(n²) brute force into an O(n log n) solution.

When to recognize this pattern

• The input is a list of intervals, usually [start, end] pairs, and the answer depends on how they overlap.
• The prompt says merge overlapping intervals, insert a new interval, or count how many ranges collide.
• You see scheduling language: meeting rooms, bookings, calendars, or "how many can run at once".
• You are asked for the fewest intervals to remove so the rest do not overlap (interval scheduling).

The overlap test and the template

Two intervals a and b overlap when a.start <= b.end and b.start <= a.end. Once you sort by start, the test simplifies: the current interval overlaps the last merged one exactly when current.start <= last.end. The canonical merge template is:

def merge(intervals):
    intervals.sort(key=lambda iv: iv[0])   # sort by start
    merged = []
    for start, end in intervals:
        if merged and start <= merged[-1][1]:
            # overlap: extend the last interval's end
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

O(n log n) time for the sort, O(n) for the pass, O(n) space for the output. The max(merged[-1][1], end) is the line most candidates forget — a later interval can start inside the group but end earlier.

Worked examples

Merge Intervals

Problem: Given a list of intervals, merge all overlapping ones and return the non-overlapping result.

This is the template above verbatim. Sort by start, then either extend the last interval or push a new one.

def merge(intervals):
    intervals.sort(key=lambda iv: iv[0])
    merged = []
    for iv in intervals:
        if merged and iv[0] <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], iv[1])
        else:
            merged.append(iv[:])
    return merged

O(n log n) time, O(n) space. Everything else in this family is a variation on this loop.

Insert Interval

Problem: Given a sorted, non-overlapping list and one new interval, insert it and merge as needed.

Because the input is already sorted, you skip the sort and do three phases in one pass: intervals entirely before the new one, intervals that overlap it (merge them), and intervals entirely after.

def insert(intervals, new):
    res, i, n = [], 0, len(intervals)
    # 1. all intervals ending before new starts
    while i < n and intervals[i][1] < new[0]:
        res.append(intervals[i]); i += 1
    # 2. merge every interval that overlaps new
    while i < n and intervals[i][0] <= new[1]:
        new[0] = min(new[0], intervals[i][0])
        new[1] = max(new[1], intervals[i][1])
        i += 1
    res.append(new)
    # 3. the rest
    while i < n:
        res.append(intervals[i]); i += 1
    return res

O(n) time, O(n) space — no sort needed since the input is pre-sorted.

Meeting Rooms II (minimum rooms)

Problem: Given meeting intervals, return the minimum number of rooms required.

This is the sweep-line in action. Split into sorted start times and end times, then walk both: a start needs a room, an end frees one.

def minMeetingRooms(intervals):
    starts = sorted(iv[0] for iv in intervals)
    ends   = sorted(iv[1] for iv in intervals)
    rooms = max_rooms = 0
    s = e = 0
    while s < len(starts):
        if starts[s] < ends[e]:
            rooms += 1          # a meeting begins
            s += 1
            max_rooms = max(max_rooms, rooms)
        else:
            rooms -= 1          # a meeting ends
            e += 1
    return max_rooms

O(n log n) time for the two sorts, O(n) space. The peak concurrent count is the answer. A min-heap of end times is an equivalent O(n log n) approach.

Non-overlapping Intervals (interval scheduling)

Problem: Find the minimum number of intervals to remove so the rest are non-overlapping.

Greedy by end time: keep the interval that finishes earliest, because it leaves the most room for what follows. Every time the next interval starts before the last kept end, remove it.

def eraseOverlapIntervals(intervals):
    intervals.sort(key=lambda iv: iv[1])   # sort by END
    removed, last_end = 0, float("-inf")
    for start, end in intervals:
        if start >= last_end:
            last_end = end          # keep it
        else:
            removed += 1            # overlaps: drop it
    return removed

O(n log n) time, O(1) extra space. Note the twist: this problem sorts by end, not start — that is the classic activity-selection greedy.

Complexity at a glance

Every problem in this family shares the same cost profile, which makes the pattern easy to reason about under time pressure. The dominant term is almost always the sort; the sweep itself is linear. Insert Interval is the exception, because its input arrives pre-sorted and needs only the single pass.

When an interviewer asks you to state the complexity, name the sort as the bottleneck and the sweep as linear — that framing signals you understand where the cost actually lives, and it generalizes to every variant you might be handed next.

Variations & pitfalls

• Sort key matters. Merging and inserting sort by start; the greedy "remove fewest" and activity-selection problems sort by end.
• Update the end with max. On a merge, always take max(last_end, current_end) — a nested interval that ends earlier must not shrink the group.
• Touching endpoints. Decide whether [1,2] and [2,3] count as overlapping. Use <= vs < deliberately and confirm the convention with your interviewer.
• Sweep-line for counts. When the question asks "how many at once" or "peak load", process start/end events rather than merging.

FAQ

When should I use the merge intervals pattern?

When the input is a list of intervals (start, end pairs) and the question asks you to merge overlaps, insert a new interval, count how many can run at once, or find the fewest to remove. Words like "meetings", "ranges", "schedule", "overlapping", or "booking" are strong signals.

What is the overlap test for two intervals?

Two intervals a and b overlap when a.start <= b.end and b.start <= a.end. If you have already sorted by start time, the check simplifies: the current interval overlaps the last merged one when its start is less than or equal to the last end.

Why do you sort intervals by start time first?

Sorting by start guarantees that any interval overlapping the current group must appear next in order, so a single left-to-right pass is enough. It turns a pairwise O(n²) comparison into an O(n log n) sort plus an O(n) sweep.

What is the sweep-line intuition?

Imagine a vertical line sweeping left to right across a timeline. You process interval starts and ends as events; a start increments the count of active intervals, an end decrements it. The maximum count reached is the peak overlap, which answers problems like minimum meeting rooms.

What is the most common merge intervals bug?

Forgetting to update the end of the merged interval to the maximum of both ends. A later interval can start inside the current group but end earlier, so you must take max(last_end, current_end) rather than blindly using the current end.