Merge Intervals Pattern 2026: 14+ Problems [Solved]

Last Updated: June 2026

Why Intervals Are a High-Frequency Topic

Candidates report interval problems in roughly 10-15% of FAANG rounds and frequently in Uber, Goldman Sachs, and calendar/scheduling product rounds. Based on public preparation resources and candidate-reported interview threads, the core merge pattern appears as the foundation in over a dozen distinct problem variants.

The key insight: most interval problems become straightforward once you sort by start time. After sorting, you only need to check one condition (current.start versus last merged interval's end) instead of checking all pairs.

Overlap Detection

Two intervals [a, b] and [c, d] (assume a <= b, c <= d):

OVERLAP if:  a <= d  AND  c <= b
NO OVERLAP if:  b < c  (first ends before second starts)
                OR  d < a  (second ends before first starts)

After sorting by start (a <= c):
  Overlap iff:  c <= b  (second starts before first ends)

Core Template: Merge Overlapping Intervals

def merge(intervals):
    """
    Sort by start time. Merge overlapping intervals.
    Time: O(n log n)  Space: O(n)
    """
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]

    for start, end in intervals[1:]:
        last_end = merged[-1][1]

        if start <= last_end:
            # Overlap: extend the last interval
            merged[-1][1] = max(last_end, end)
        else:
            # No overlap: add new interval
            merged.append([start, end])

    return merged

Practice Questions with Solutions

Problem 1: Merge Intervals (MEDIUM)

Asked at: Amazon, Google, Microsoft, Facebook

def merge_intervals(intervals):
    """
    Sort + sweep. Standard template.
    Time: O(n log n)  Space: O(n)
    """
    if not intervals:
        return []

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

    for i in range(1, len(intervals)):
        curr = intervals[i]
        if curr[0] <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], curr[1])
        else:
            merged.append(curr[:])

    return merged

# Example
print(merge_intervals([[1,3],[2,6],[8,10],[15,18]]))  # [[1,6],[8,10],[15,18]]
print(merge_intervals([[1,4],[4,5]]))                  # [[1,5]]

Complexity: Time O(n log n), Space O(n)

Problem 2: Insert Interval (MEDIUM)

Asked at: Amazon, Google, Microsoft - requires careful case handling

def insert(intervals, new_interval):
    """
    Three phases: before overlap, merge overlap, after overlap.
    Time: O(n)  Space: O(n) - list is already sorted
    """
    result = []
    i = 0
    n = len(intervals)

    # Phase 1: Add all intervals that end before new_interval starts
    while i < n and intervals[i][1] < new_interval[0]:
        result.append(intervals[i])
        i += 1

    # Phase 2: Merge all overlapping intervals
    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)

    # Phase 3: Add remaining intervals
    while i < n:
        result.append(intervals[i])
        i += 1

    return result

# Example
print(insert([[1,3],[6,9]], [2,5]))       # [[1,5],[6,9]]
print(insert([[1,2],[3,5],[6,7],[8,10],[12,16]], [4,8]))  # [[1,2],[3,10],[12,16]]

Complexity: Time O(n), Space O(n)

Problem 3: Non-overlapping Intervals (MEDIUM)

Asked at: Amazon, Google, Microsoft

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

def erase_overlap_intervals(intervals):
    """
    Greedy: sort by end time. Always keep the interval with smallest end.
    When overlap found, remove the one with larger end (greedy keeps smaller end).
    Time: O(n log n)  Space: O(1)
    """
    if not intervals:
        return 0

    intervals.sort(key=lambda x: x[1])  # sort by END time
    count = 0
    prev_end = intervals[0][1]

    for i in range(1, len(intervals)):
        if intervals[i][0] < prev_end:
            # Overlap: remove current (it has larger or equal end)
            count += 1
        else:
            prev_end = intervals[i][1]

    return count

# Example
print(erase_overlap_intervals([[1,2],[2,3],[3,4],[1,3]]))  # 1 (remove [1,3])
print(erase_overlap_intervals([[1,2],[1,2],[1,2]]))         # 2

Complexity: Time O(n log n), Space O(1)

Key insight: Sorting by end time (not start) is the greedy choice here. The interval with the earliest end leaves maximum room for subsequent intervals.

Problem 4: Meeting Rooms (EASY)

Asked at: Amazon, Google, Microsoft, Uber

Problem: Given meeting time intervals, can one person attend all meetings?

def can_attend_meetings(intervals):
    """
    Sort by start time. If any two adjacent intervals overlap, impossible.
    Time: O(n log n)  Space: O(1)
    """
    intervals.sort(key=lambda x: x[0])

    for i in range(1, len(intervals)):
        if intervals[i][0] < intervals[i-1][1]:
            return False

    return True

# Example
print(can_attend_meetings([[0,30],[5,10],[15,20]]))  # False (overlap at 5-10 with 0-30)
print(can_attend_meetings([[7,10],[2,4]]))            # True

Complexity: Time O(n log n), Space O(1)

Problem 5: Meeting Rooms II - Minimum Rooms (MEDIUM)

Asked at: Amazon, Google, Uber, Goldman Sachs - very frequently asked

Problem: Find minimum number of conference rooms required.

def min_meeting_rooms(intervals):
    """
    Split into sorted start and end arrays.
    Two pointer: count rooms in use at any time.
    Time: O(n log n)  Space: O(n)
    """
    starts = sorted(i[0] for i in intervals)
    ends = sorted(i[1] for i in intervals)

    rooms = 0
    max_rooms = 0
    s = e = 0

    while s < len(intervals):
        if starts[s] < ends[e]:
            rooms += 1
            max_rooms = max(max_rooms, rooms)
            s += 1
        else:
            rooms -= 1
            e += 1

    return max_rooms

# Example
print(min_meeting_rooms([[0,30],[5,10],[15,20]]))  # 2
print(min_meeting_rooms([[7,10],[2,4]]))            # 1

Complexity: Time O(n log n), Space O(n)

Heap alternative: Use a min-heap of end times. For each new meeting, if it starts after heap top ends, replace. Otherwise, add new room. Same complexity, more intuitive.

def min_meeting_rooms_heap(intervals):
    import heapq

    intervals.sort(key=lambda x: x[0])
    heap = []  # end times

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

    return len(heap)

Problem 6: Interval List Intersections (MEDIUM)

Asked at: Amazon, Google, Facebook

def interval_intersection(first_list, second_list):
    """
    Two pointers on both sorted lists.
    Intersection of [a,b] and [c,d] = [max(a,c), min(b,d)] if max <= min.
    Advance the pointer with smaller end.
    Time: O(m+n)  Space: O(m+n)
    """
    result = []
    i = j = 0

    while i < len(first_list) and j < len(second_list):
        lo = max(first_list[i][0], second_list[j][0])
        hi = min(first_list[i][1], second_list[j][1])

        if lo <= hi:
            result.append([lo, hi])

        # Advance the interval that ends first
        if first_list[i][1] < second_list[j][1]:
            i += 1
        else:
            j += 1

    return result

# Example
print(interval_intersection([[0,2],[5,10],[13,23],[24,25]],
                              [[1,5],[8,12],[15,24],[25,26]]))
# [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

Complexity: Time O(m+n), Space O(m+n)

Problem 7: Employee Free Time (HARD)

Asked at: Google, Uber, Facebook

Problem: Given a list of employees, each with a list of non-overlapping working intervals, find all free time intervals (time not covered by any employee).

def employee_free_time(schedule):
    """
    Flatten all intervals, sort by start, find gaps.
    Time: O(n log n)  Space: O(n)
    """
    # Flatten all employee schedules
    intervals = []
    for employee in schedule:
        for interval in employee:
            intervals.append(interval)

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

    # Find gaps using merge logic
    free = []
    prev_end = intervals[0][1]

    for i in range(1, len(intervals)):
        start, end = intervals[i]
        if start > prev_end:
            free.append([prev_end, start])
        prev_end = max(prev_end, end)

    return free

# Example
schedule = [[[1,3],[6,7]], [[2,4]], [[2,5],[9,12]]]
print(employee_free_time(schedule))  # [[5,6],[7,9]]

Complexity: Time O(n log n), Space O(n)

Problem 8: Minimum Number of Arrows to Burst Balloons (MEDIUM)

Asked at: Amazon, Google

def find_min_arrow_shots(points):
    """
    Sort by end. Shoot as far right as possible (at interval end).
    A new arrow needed when current balloon starts after last arrow.
    This is identical in structure to non-overlapping intervals.
    Time: O(n log n)  Space: O(1)
    """
    points.sort(key=lambda x: x[1])
    arrows = 1
    arrow_pos = points[0][1]

    for start, end in points[1:]:
        if start > arrow_pos:
            arrows += 1
            arrow_pos = end

    return arrows

# Example
print(find_min_arrow_shots([[10,16],[2,8],[1,6],[7,12]]))  # 2
print(find_min_arrow_shots([[1,2],[3,4],[5,6],[7,8]]))      # 4

Complexity: Time O(n log n), Space O(1)

Problem 9: Car Pooling (MEDIUM)

Asked at: Amazon, Lyft - the sweep-line variant

Problem: A car has a fixed capacity. Given trips as (passengers, start, end), return whether all trips fit without exceeding capacity.

def car_pooling(trips, capacity):
    """
    Sweep line / difference array on the location axis.
    Add passengers at start, remove at end, check running load.
    Time: O(n + max_loc)  Space: O(max_loc)
    """
    timeline = [0] * 1001
    for passengers, start, end in trips:
        timeline[start] += passengers
        timeline[end] -= passengers

    load = 0
    for delta in timeline:
        load += delta
        if load > capacity:
            return False
    return True

# Example
print(car_pooling([[2,1,5],[3,3,7]], 4))   # False (load 5 at point 3)
print(car_pooling([[2,1,5],[3,3,7]], 5))   # True

Dry run: at location 1 we add 2, at location 3 we add 3 (load becomes 5), and at location 5 we drop 2. With capacity 4, the load of 5 between points 3 and 5 fails. The difference-array trick turns each interval into two point updates, which is the sweep-line essence.

Complexity: Time O(n + range), Space O(range)

Problem 10: My Calendar I (MEDIUM)

Asked at: Google, Amazon

Problem: Implement a book(start, end) that returns False if the new event overlaps any existing event, True otherwise (and books it).

class MyCalendar:
    """
    Keep booked intervals. A new [s, e) conflicts with [bs, be)
    iff s < be and bs < e. Linear scan per booking.
    Time: O(n) per book  Space: O(n)
    """
    def __init__(self):
        self.events = []

    def book(self, start, end):
        for bs, be in self.events:
            if start < be and bs < end:    # overlap test
                return False
        self.events.append((start, end))
        return True

# Example
cal = MyCalendar()
print(cal.book(10, 20))   # True
print(cal.book(15, 25))   # False (overlaps 10-20)
print(cal.book(20, 30))   # True (touching at 20 is allowed)

The overlap condition start < be and bs < end is the single most reused predicate in interval problems. Memorize it: two half-open intervals overlap exactly when each starts before the other ends.

Complexity: Time O(n) per booking, Space O(n)

Problem 11: Remove Covered Intervals (MEDIUM)

Asked at: Amazon, Microsoft

Problem: Remove intervals that are fully covered by another interval; return the count remaining.

def remove_covered_intervals(intervals):
    """
    Sort by start ascending, end descending for ties.
    An interval is covered if its end <= the max end seen so far.
    Time: O(n log n)  Space: O(1)
    """
    intervals.sort(key=lambda x: (x[0], -x[1]))
    remaining = 0
    prev_end = 0
    for start, end in intervals:
        if end > prev_end:
            remaining += 1
            prev_end = end
        # else: this interval is covered, skip it
    return remaining

# Example
print(remove_covered_intervals([[1,4],[3,6],[2,8]]))   # 2 ([1,4] is not covered, [3,6] is by [2,8])

The tie-break (end descending when starts are equal) is essential: it ensures the larger interval is processed first so the smaller equal-start interval is correctly seen as covered.

Complexity: Time O(n log n), Space O(1)

Problem 12: Data Stream as Disjoint Intervals (HARD)

Asked at: Google, Amazon

Problem: Add integers from a stream and report the merged disjoint intervals so far.

import bisect

class SummaryRanges:
    """
    Maintain sorted disjoint intervals. On addNum, binary-search the
    insertion point and merge with neighbors if they become adjacent.
    Time: addNum O(n) worst (list shift)  Space: O(n)
    """
    def __init__(self):
        self.intervals = []

    def add_num(self, val):
        ivs = self.intervals
        i = bisect.bisect_left(ivs, [val, val])
        # Check merge with left and right neighbors
        start, end = val, val
        # Merge left
        if i > 0 and ivs[i-1][1] + 1 >= val:
            i -= 1
            start = ivs[i][0]
            end = max(end, ivs[i][1])
        # Merge right while overlapping/adjacent
        while i < len(ivs) and ivs[i][0] <= end + 1:
            end = max(end, ivs[i][1])
            ivs.pop(i)
        ivs.insert(i, [start, end])

    def get_intervals(self):
        return self.intervals

# Example
sr = SummaryRanges()
for n in [1, 3, 7, 2, 6]:
    sr.add_num(n)
print(sr.get_intervals())   # [[1,3],[6,7]]

Complexity: Time O(n) per add (list shift), Space O(n)

How to Recognize a Merge Intervals Problem

The pattern is unmistakable once you learn its signals. Reach for the interval toolkit when the input is a list of pairs representing ranges (start, end), times, or segments on a line.

If the question asks you to combine, merge, or find overlaps among ranges, sort by start time and sweep, merging any interval whose start is at or before the running maximum end. This is the base merge operation that problems 1, 2, and 7 all reduce to.

If the question asks for the minimum count of something (rooms, arrows, removals) or the maximum number of non-conflicting intervals, it is a greedy problem: sort by end time and make the earliest-finishing choice. Problems 3, 5, and 8 are this Activity Selection family.

If the question asks how many things are simultaneously active at a peak (rooms needed, passengers in a car), it is a sweep-line or difference-array problem: turn each interval into a plus event at start and a minus event at end, then scan the running total. Problems 5 and 9 are this family.

The reusable overlap predicate to keep in your head is: two intervals [a, b) and [c, d) overlap exactly when a is less than d and c is less than b. Almost every interval problem is built on top of that single test plus the right sort order.

Sort by Start vs Sort by End: When to Use Each

The Greedy Pattern in Interval Problems

Many interval optimization problems follow a greedy framework: sort by end time, then make the locally optimal choice (keep the interval with the earliest end). This greedy works because the interval with the smallest end time leaves maximum space for future intervals.

This is the Activity Selection Problem from algorithm theory. When an interviewer asks for the intuition behind sorting by end instead of start, the answer is: we want to maximize the number of non-conflicting intervals, so we greedily commit to the one that frees up time the earliest.

The meeting rooms problem is the dual: instead of maximizing non-conflicting intervals, we count the maximum simultaneous overlap, which equals the minimum rooms needed. The two-pointer approach on split start and end arrays gives a clean O(n) implementation after O(n log n) sorting.

Complexity Summary

Related Articles

• Sorting Questions Placement
• Two Pointers Pattern Questions 2026
• Greedy Questions Placement
• Must-Do Coding Questions
• System Design Interview Questions 2026