Interval Problems: Merge, Insert, and Overlap Patterns

Interval problems are a favorite in coding interviews because they look simple — you're just dealing with pairs of numbers — but the edge cases are tricky and the patterns aren't immediately obvious if you haven't seen them before.

The core insight for almost every interval problem: sort the intervals first. Once they're sorted, you can process them left to right in a single pass, and the problems become much more manageable.

When You'll See Interval Problems

Interval problems show up in scheduling contexts (meeting rooms, event conflicts), range merging (overlapping time ranges, IP ranges), and resource allocation. They're common at medium difficulty and sometimes appear as the first step of a harder problem.

The problems tend to be short to implement but require careful handling of edge cases — which is exactly what interviewers want to evaluate.

The Foundation: Sorting Intervals

Almost every interval problem starts with sorting. Usually you sort by start time:

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

Sometimes you sort by end time (for greedy scheduling problems). The right sort order depends on the problem, but start time is the default.

After sorting, intervals that could potentially overlap are adjacent, which means you can solve most problems in a single left-to-right pass.

Pattern 1: Merge Overlapping Intervals

Problem: Given a collection of intervals, merge all overlapping intervals.

Example: [[1,3], [2,6], [8,10], [15,18]] becomes [[1,6], [8,10], [15,18]].

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

for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            # overlapping — extend the current interval
            merged[-1][1] = max(merged[-1][1], end)
        else:
            # no overlap — start a new interval
            merged.append([start, end])

return merged

The key decision: two intervals overlap if the start of the second is less than or equal to the end of the first. When they overlap, extend the current interval's end to cover both. When they don't, start a new interval.

O(n log n) for sorting, O(n) for the merge pass.

Common edge cases:

• Intervals that touch but don't overlap: [1,2] and [2,3]. Whether these are considered overlapping depends on the problem. In "merge intervals," they usually are (since the boundary is shared).
• One interval completely contained within another: [1,10] and [3,5]. The merge naturally handles this — the outer interval's end is already larger.
• Single interval: return it as-is.
• Empty input: handle at the start.

Pattern 2: Insert Interval

Problem: Given a sorted list of non-overlapping intervals and a new interval, insert the new interval and merge if necessary.

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

# add all intervals that come before new_interval
    while i < n and intervals[i][1] < new_interval[0]:
        result.append(intervals[i])
        i += 1

# merge all overlapping intervals with new_interval
    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)

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

return result

Three phases: everything before the overlap, the merged overlap, everything after. Clean and O(n).

The overlap condition is the same as in merge intervals: an interval overlaps with new_interval if its start is <= new_interval's end AND its end is >= new_interval's start. But since the input is sorted and we've already skipped non-overlapping intervals from the left, we only need to check intervals[i][0] <= new_interval[1].

Pattern 3: Meeting Rooms

Meeting Rooms I: Can One Person Attend All Meetings?

Given a list of meeting intervals, determine if a person can attend all meetings (i.e., no two meetings overlap).

def can_attend_meetings(intervals):
    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

Sort by start time. If any meeting starts before the previous one ends, there's a conflict.

Meeting Rooms II: Minimum Conference Rooms

Given meeting intervals, find the minimum number of conference rooms required.

Approach 1: Min-Heap

import heapq

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

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

for start, end in intervals:
        if heap and heap[0] <= start:
            heapq.heappop(heap)  # room freed up
        heapq.heappush(heap, end)

return len(heap)

The heap tracks the end times of all ongoing meetings. For each new meeting, if the earliest-ending meeting has already finished (its end time <= the new meeting's start), we reuse that room (pop it). Otherwise, we need a new room. The size of the heap at any point is the number of rooms in use.

O(n log n).

Approach 2: Sweep Line (Event-Based)

def min_meeting_rooms_sweep(intervals):
    events = []
    for start, end in intervals:
        events.append((start, 1))   # meeting starts
        events.append((end, -1))    # meeting ends

events.sort()

rooms = 0
    max_rooms = 0
    for time, delta in events:
        rooms += delta
        max_rooms = max(max_rooms, rooms)

return max_rooms

Create events for each start (+1 room) and end (-1 room). Sort all events by time. Walk through them, tracking the running total. The maximum total is the answer.

This is the sweep line technique, and it's incredibly versatile. More on it below.

Pattern 4: Minimum Platforms (Train Station)

Problem: Given arrival and departure times of trains, find the minimum number of platforms needed at a station so no train waits.

This is exactly Meeting Rooms II with a different name. Either the heap approach or the sweep line approach works.

def min_platforms(arrivals, departures):
    events = []
    for a in arrivals:
        events.append((a, 1))
    for d in departures:
        events.append((d, -1))

events.sort()

platforms = 0
    max_platforms = 0
    for time, delta in events:
        platforms += delta
        max_platforms = max(max_platforms, platforms)

return max_platforms

Tie-breaking note: If a train departs at time 10 and another arrives at time 10, the departure should be processed first (they can share the platform). This depends on problem specifications. In the sort, if the times are equal, process departures (-1) before arrivals (+1) — which happens naturally here since -1 < 1.

Pattern 5: Interval Intersection

Problem: Given two lists of sorted, non-overlapping intervals, return their intersection.

def interval_intersection(A, B):
    result = []
    i = j = 0

while i < len(A) and j < len(B):
        # find overlap
        start = max(A[i][0], B[j][0])
        end = min(A[i][1], B[j][1])

if start <= end:
            result.append([start, end])

# advance the pointer with the smaller end
        if A[i][1] < B[j][1]:
            i += 1
        else:
            j += 1

return result

Two pointers, one for each list. At each step, check if the current intervals overlap (the later start is before the earlier end). The overlap is [max(starts), min(ends)]. Advance the pointer whose interval ends first, since that interval can't overlap with anything else.

O(n + m) time, which is optimal since you must look at every interval at least once.

Pattern 6: Sweep Line Technique

The sweep line (or event-based) approach is a general technique that works for many interval problems. The idea:

1. Convert intervals into events (start event, end event)
2. Sort events by time
3. Process events left to right, maintaining some state

We already saw this for meeting rooms. Here are more applications.

Problem: Employee Free Time

Given a list of schedules (each employee has a sorted list of non-overlapping working intervals), find the common free time for all employees.

def employee_free_time(schedules):
    events = []
    for schedule in schedules:
        for start, end in schedule:
            events.append((start, 1))
            events.append((end, -1))

events.sort()

result = []
    active = 0
    prev_time = None

for time, delta in events:
        if active == 0 and prev_time is not None and prev_time < time:
            result.append([prev_time, time])
        active += delta
        if active == 0:
            prev_time = time

return result

Track how many employees are working. When the count drops to 0, record the time. When it rises above 0 again, record the free time gap.

Problem: Maximum Overlapping Intervals at Any Point

What's the maximum number of intervals that overlap at any single point?

def max_overlap(intervals):
    events = []
    for start, end in intervals:
        events.append((start, 1))
        events.append((end, -1))

events.sort()

current = 0
    maximum = 0
    for time, delta in events:
        current += delta
        maximum = max(maximum, current)

return maximum

This is the same as meeting rooms II. The sweep line naturally tracks the overlap count.

Problem: Points Covered by Most Intervals

Given intervals, which integer point is covered by the most intervals?

Use the sweep line to find the moment of maximum overlap. Any point in that interval works.

Pattern 7: Non-Overlapping Interval Selection (Greedy)

Problem: Given intervals, find the minimum number of intervals to remove so that the remaining intervals don't overlap.

This is equivalent to: find the maximum number of non-overlapping intervals (activity selection problem). Then the answer is total - max_non_overlapping.

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

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

return len(intervals) - count

Sort by end time, not start time. Greedily pick the interval that ends earliest — this leaves the most room for future intervals. This is the classic activity selection greedy algorithm.

Why sort by end time? If you sort by start time, you might pick a long interval that blocks many short ones. Sorting by end time ensures you always make the locally optimal choice.

Problem: Minimum Number of Arrows to Burst Balloons

Balloons are intervals on a number line. An arrow shot at position x bursts all balloons where start <= x <= end. Find the minimum number of arrows.

def find_min_arrow_shots(points):
    points.sort(key=lambda x: x[1])  # sort by end
    arrows = 0
    prev_end = float('-inf')

for start, end in points:
        if start > prev_end:
            arrows += 1
            prev_end = end

return arrows

Same greedy approach. Each "group" of overlapping balloons needs one arrow. Place the arrow at the end of the earliest-ending balloon in each group.

Common Mistakes

Not sorting first. Almost every interval problem requires sorting. If you're processing unsorted intervals, you're probably making it harder than it needs to be. Wrong sort key. Merge problems sort by start time. Greedy selection problems sort by end time. Using the wrong one gives wrong answers. Confusion about overlap boundaries. Does [1,2] overlap with [2,3]? It depends on the problem. Sometimes the boundary is inclusive (they overlap at point 2), sometimes exclusive (they don't overlap). Read the problem statement carefully. Not handling the last interval. When building a result in a single pass, make sure you process the last interval. A common bug: the loop ends before adding the final merged interval to the result. Using sorting when a heap would be more efficient. For problems like Meeting Rooms II where you process intervals sequentially and need to track the minimum end time, a heap gives you O(log n) per operation. Re-sorting on each step would be O(n log n) per step.

Practice Problems

Merge/Insert: Merge Intervals, Insert Interval, Interval List Intersections Meeting Rooms: Meeting Rooms, Meeting Rooms II, Minimum Platforms Greedy Selection: Non-overlapping Intervals, Minimum Number of Arrows to Burst Balloons, Maximum Length of Pair Chain Sweep Line: Employee Free Time, My Calendar I/II/III, Car Pooling

Work through these problems on CodeUp — start with merge intervals to build the core intuition, then tackle the greedy problems where the sort order matters more.