Interval Problems in Coding Interviews: Merge, Insert & Overlap Patterns

Interval problems show up in nearly every FAANG interview loop. They test whether you can reason about overlapping ranges, sort correctly, and handle edge cases without off-by-one errors. Master three core patterns — merge, insert, and erase — and you'll handle any interval question thrown at you.

When to Use Interval Patterns

You're dealing with an interval problem when the input contains pairs of numbers representing ranges [start, end] and you need to:

• Merge overlapping ranges into fewer, larger ranges
• Insert a new interval into a sorted list of non-overlapping ranges
• Count or erase overlapping intervals (e.g., minimum deletions to remove all overlaps)
• Find gaps between intervals
• Schedule or partition resources by time

The trigger signals: the word "interval," "range," "meeting," "schedule," or "overlap" in the problem statement. Input is almost always a list of [start, end] pairs.

The universal first step: Sort intervals by start time. This converts a chaotic list into a linear scan problem.

Pattern 1: Merge Intervals

After sorting by start time, iterate through the list. If the current interval overlaps with the previous one (current start <= previous end), merge them by extending the previous end to max(prev_end, curr_end).

Example: Merge Overlapping Intervals

def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]

    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])

    return merged

Walkthrough with [[1,3],[2,6],[8,10],[15,18]]:

1. Sort → [[1,3],[2,6],[8,10],[15,18]] (already sorted)
2. Start with [1,3]
3. [2,6] overlaps (2 ≤ 3) → merge to [1,6]
4. [8,10] doesn't overlap (8 > 6) → append
5. [15,18] doesn't overlap (15 > 10) → append
6. Result: [[1,6],[8,10],[15,18]]

Time: O(n log n) for the sort. Space: O(n) for the result list.

Common Mistake: Using end Instead of max(prev_end, curr_end)

# WRONG — fails when new interval ends after the current merged interval
merged[-1][1] = end

# CORRECT — takes the larger end
merged[-1][1] = max(merged[-1][1], end)

Pattern 2: Insert Interval

You're given a sorted list of non-overlapping intervals and a new interval. Insert it, merging as needed. This is a three-phase scan:

1. Add all intervals that end before the new interval starts (no overlap)
2. Merge all overlapping intervals with the new interval
3. Add all intervals that start after the merged result

Example: Insert Interval

def insert(intervals, new_interval):
    result = []
    i = 0
    n = len(intervals)

    while i < n and intervals[i][1] < new_interval[0]:
        result.append(intervals[i])
        i += 1

    while i < n and intervals[i][0] <= new_interval[1]:
        new_interval[0] = min(new_interval[0], intervals[i][0])
        new_interval[1] = max(new_interval[1], intervals[i][1])
        i += 1

    result.append(new_interval)

    while i < n:
        result.append(intervals[i])
        i += 1

    return result

Walkthrough with [[1,3],[6,9]] and new = [2,5]:

1. [1,3] — 3 < 2 is false, so we enter the merge loop
2. [1,3] overlaps (1 ≤ 5) → merge to [min(2,1), max(5,3)] = [1,5]
3. [6,9] — 6 > 5, exit merge loop
4. Append [1,5], then append [6,9]
5. Result: [[1,5],[6,9]]

Time: O(n). Space: O(n).

Pattern 3: Non-Overlapping Intervals (Erase to Minimize)

Given a list of intervals, find the minimum number you need to remove so the rest don't overlap. The greedy insight: always keep the interval that ends earliest, because it leaves the most room for future intervals.

Example: Minimum Removals for Non-Overlapping

def erase_overlap_intervals(intervals):
    intervals.sort(key=lambda x: x[1])
    count = 0
    prev_end = float('-inf')

    for start, end in intervals:
        if start >= prev_end:
            prev_end = end
        else:
            count += 1

    return count

Walkthrough with [[1,2],[2,3],[3,4],[1,3]]:

1. Sort by end: [[1,2],[1,3],[2,3],[3,4]]
2. [1,2] — 1 ≥ -∞ → keep, prev_end = 2
3. [1,3] — 1 < 2 → remove (count = 1)
4. [2,3] — 2 ≥ 2 → keep, prev_end = 3
5. [3,4] — 3 ≥ 3 → keep, prev_end = 4
6. Result: 1 removal

Time: O(n log n). Space: O(1).

Pattern 4: Meeting Rooms II (Minimum Resources)

Count the maximum number of simultaneous intervals. The trick: treat each start and end as separate events, sort them, and sweep through. When a start event arrives, increment the count. When an end event arrives, decrement.

import heapq

def min_meeting_rooms(intervals):
    if not intervals:
        return 0

    intervals.sort(key=lambda x: x[0])
    heap = [intervals[0][1]]

    for start, end in intervals[1:]:
        if heap[0] <= start:
            heapq.heapreplace(heap, end)
        else:
            heapq.heappush(heap, end)

    return len(heap)

Walkthrough with [[0,30],[5,10],[15,20]]:

1. Sort by start: [[0,30],[5,10],[15,20]]
2. Push 30 → heap = [30]
3. 5 < 30 → push 10 → heap = [10,30]
4. 15 > 10 → replace → heap = [20,30]
5. Result: 2 rooms needed

Time: O(n log n). Space: O(n).

Complexity Summary

Common Mistakes

1. Not sorting first. Without sorting, you can't guarantee the linear scan works. Always sort by start time (or end time for greedy problems).

2. Off-by-one on overlap check. Intervals [1,2] and [2,3] may or may not overlap depending on whether endpoints are inclusive. Clarify with the interviewer. The standard convention: [start, end) — start is inclusive, end is exclusive.

3. Comparing against the last added interval. When merging, always compare against merged[-1], not the current raw interval.

4. Forgetting to handle empty input. Check if not intervals before accessing intervals[0].

5. Using end instead of max(prev_end, curr_end) in merge. This breaks when a new interval is entirely contained within an existing merged interval.

Practice Problems

These problems test the core interval patterns. Solve them in order — each builds on the previous.

1. Merge Intervals — The foundational merge pattern. Given a list of intervals, merge all overlapping ones.

2. Insert Interval — Three-phase scan with merge. A sorted non-overlapping list plus one new interval.

3. Non-overlapping Intervals — Greedy erase. Find minimum removals so no overlaps remain.

4. Meeting Rooms II — Count maximum simultaneous overlaps using a heap or event sweep.

5. Interval List Intersections — Two-pointer merge of two sorted interval lists. Output only the intersection segments.

Ready to Practice?

Interval problems are deceptively simple — the sorting step is obvious, but edge cases in merging, insertion, and overlap checks trip up even experienced candidates. The best way to prepare is to solve these problems under real interview conditions.

Start a mock coding interview →

Alex, the AI interviewer on InterviewSkool, will present interval problems, ask follow-up questions about your edge case handling, and evaluate your communication — exactly what happens in a FAANG interview.

Frequently Asked Questions