Home / Blog / Merge Intervals Interview Pattern

Merge Intervals Interview Pattern

Published 2026-10-09 · Luna Interview

Interval problems look like a pile of edge cases until you lock the merge intervals interview pattern: sort by start time, then sweep once while merging overlaps into a result list. From that core you derive insert-interval, meeting-room counts, and “can attend all” checks without reinventing the wheel.

The 10-second classification

Ask:

1. Are these closed/open intervals on a line (time, ranges of integers)?
2. Do I need to merge overlaps, insert one range, count concurrent, or detect any overlap?
3. Is sorting by start (sometimes by end) allowed? Usually yes—confirm mutability.
4. How do ties and touching endpoints count—[1,2] and [2,3] merge or not?

Talk track:

“I’ll sort by start, then scan: if the next interval overlaps the current end, extend the end; otherwise push a new interval. I’ll confirm whether touching endpoints count as overlap.”

That last clarification prevents silent off-by-ones.

Core merge template

def merge(intervals):
    if not intervals:
        return []
    intervals = sorted(intervals, key=lambda x: x[0])
    merged = [intervals[0][:]]  # copy
    for start, end in intervals[1:]:
        last = merged[-1]
        if start <= last[1]:          # overlap or touch; use < if touch should not merge
            last[1] = max(last[1], end)
        else:
            merged.append([start, end])
    return merged

Narrate the invariant:

“merged always holds disjoint intervals sorted by start. The only interval that can overlap the new one is the last.”

When to use < vs <=

• Inclusive intervals where [1,2] and [2,3] should become [1,3] → start <= last[1]
• Half-open [start, end) where touching ends do not overlap → often start < last[1] for “overlap,” and merge rule follows the problem statement

Write the problem’s rule on the pad before coding.

Pattern: insert a new interval

1. Add all intervals that end before the new one starts.
2. Merge all that overlap the new interval into an expanded new interval.
3. Append the rest.

def insert(intervals, new):
    res = []
    i, n = 0, len(intervals)
    ns, ne = new

    while i < n and intervals[i][1] < ns:
        res.append(intervals[i])
        i += 1
    while i < n and intervals[i][0] <= ne:
        ns = min(ns, intervals[i][0])
        ne = max(ne, intervals[i][1])
        i += 1
    res.append([ns, ne])
    while i < n:
        res.append(intervals[i])
        i += 1
    return res

Talk track:

“Left of new, merge through overlaps, then right. Still one linear pass after assuming input sorted—or sort first if needed.”

Pattern: can attend all meetings

Sort by start; check each adjacent pair for overlap:

def can_attend(intervals):
    intervals = sorted(intervals, key=lambda x: x[0])
    for i in range(1, len(intervals)):
        if intervals[i][0] < intervals[i - 1][1]:
            return False
    return True

Adjust < vs <= to the touching rule.

Pattern: meeting rooms / min concurrency

Sweep line: treat starts as +1, ends as -1, sort events (process ends before starts at the same time if meetings can back-to-back).

def min_meeting_rooms(intervals):
    events = []
    for s, e in intervals:
        events.append((s, 1))
        events.append((e, -1))
    # ends (-1) before starts (+1) at equal time
    events.sort(key=lambda x: (x[0], x[1]))
    cur = best = 0
    for _, delta in events:
        cur += delta
        best = max(best, cur)
    return best

Talk track:

“I’ll convert to a sweep on endpoints. Sorting end events before start events at the same timestamp allows immediate reuse of a room.”

Candidates commonly report meeting-room variants in scheduling-themed rounds. Keep discussion pattern-level; do not invent confidential company prompts.

Pattern: intersection of two interval lists

Two pointers on two sorted disjoint lists: advance the one with the smaller end; record overlap when max(starts) < min(ends) (or <= per rules).

This is still the interval family—sorting and pointer movement—not merge of one list alone.

Common bugs

• Forgetting to sort
• Comparing to merged[0] instead of merged[-1]
• Using min on ends instead of max when extending
• Mutating the input interval objects unexpectedly
• Wrong touch rule (<= vs <)
• Sweep line: processing starts before ends at equal time when reuse is allowed
• Empty input / single interval not handled

Complexity to state

Sort O(n log n), then O(n) merge. Sweep for rooms is O(n log n) on 2n events. Mention you cannot beat sorting in the comparison model for arbitrary intervals if order is required.

First five minutes

1. Clarify inclusive bounds and touching
2. Sort by start (or explain sweep events)
3. Write the merge invariant in one sentence
4. Dry-run [[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]]
5. Note O(n log n)

Soft practice note

Interval bugs are usually boundary calls under pressure. If you want calm, timed practice narrating sort-then-sweep before the real round, Luna Interview is built for structured interview rehearsal and composure—not for anything that violates interview rules.

Day-of checklist

• [ ] Touch/overlap rule confirmed
• [ ] Sorted by start (or events sorted with tie-break)
• [ ] Extend with max end
• [ ] Only compare against last merged interval
• [ ] Insert-interval: before / merge / after
• [ ] Dry-ran a touching-endpoint pair

Sort, sweep, merge the last open range—that is the pattern. Everything else is a costume on top of it.

Rehearse with an AI interview copilot, then browse commonly reported interview questions.