Overlapping Intervals Pattern | CodeTutor

Overlapping Intervals

Easy

4 questions using this pattern

What is Overlapping Intervals?

Process and manipulate intervals (ranges) that may share common regions. The key insight is that sorting intervals by start time allows efficient detection and handling of overlaps through a single linear pass.

Think of it like this...

Imagine scheduling meeting rooms. Each meeting is an interval of time. When two meetings overlap, you need either two rooms or to merge them into one longer booking. By sorting meetings by start time, you can easily spot overlaps—if the next meeting starts before the current one ends, they overlap.

Another analogy: merging overlapping highlighter marks on a page. Sort them left to right, and if one mark starts before the previous ends, combine them into one continuous highlight.

Core Concept

The interval pattern relies on sorting intervals by start time. Once sorted, overlapping detection becomes simple:

Two intervals [a, b] and [c, d] overlap if c <= b (assuming a <= c after sorting)

Key operations:

Merge: Extend the current interval's end to include overlapping intervals
Insert: Find where the new interval overlaps and merge as needed
Count overlaps: Track how many intervals are "active" at any point

For problems needing simultaneous tracking (like minimum meeting rooms), use a sweep line approach: sort all start and end points together, then sweep through counting active intervals.

Merge Intervals

Intervals

def merge(intervals: list[list[int]]) -> list[list[int]]:

    if len(intervals) <= 1:

        return intervals

    # Sort by start time

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

    merged = [intervals[0]]

    for current in intervals[1:]:

        last = merged[-1]

        if current[0] <= last[1]:  # Overlap

            last[1] = max(last[1], current[1])

        else:

            merged.append(current)

    return merged

Variables

No variables yet

Input Intervals (sorted)

[1,3]

[8,10]

[15,18]

[2,6]

Problem

Given intervals [[1,3], [2,6], [8,10], [15,18]], merge all overlapping intervals. Notice [1,3] and [2,6] share the range [2,3].

1/19

Visual Walkthrough

Merging overlapping intervals:

Input: [[1,3], [2,6], [8,10], [15,18]]
       (sorted by start)

Process [1,3]: result = [[1,3]]

Process [2,6]: 2 <= 3? Yes, overlap!
               Merge: [1, max(3,6)] = [1,6]
               result = [[1,6]]

Process [8,10]: 8 <= 6? No, no overlap
                result = [[1,6], [8,10]]

Process [15,18]: 15 <= 10? No, no overlap
                 result = [[1,6], [8,10], [15,18]]

Visualized on number line:

Before:  [1---3]
            [2------6]
                        [8--10]
                                   [15--18]

After:   [1--------6]  [8--10]     [15--18]

Meeting rooms (sweep line):

Meetings: [[0,30], [5,10], [15,20]]

Events (sorted):
time=0:  +1 (start)  active=1
time=5:  +1 (start)  active=2 ← max
time=10: -1 (end)    active=1
time=15: +1 (start)  active=2 ← max
time=20: -1 (end)    active=1
time=30: -1 (end)    active=0

Max concurrent = 2 → need 2 meeting rooms

Code Template

Use this skeleton as a starting point for problems using this pattern:

python

def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
    """Merge overlapping intervals."""
    if not intervals:
        return []

    # Sort by start time
    intervals.sort(key=lambda x: x[0])

    result = [intervals[0]]

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

        if start <= last_end:  # Overlap
            result[-1][1] = max(last_end, end)  # Extend
        else:
            result.append([start, end])

    return result


def insert_interval(intervals: list[list[int]],
                    new: list[int]) -> list[list[int]]:
    """Insert and merge a new interval into sorted list."""
    result = []
    i = 0
    n = len(intervals)

    # Add all intervals before new interval
    while i < n and intervals[i][1] < new[0]:
        result.append(intervals[i])
        i += 1

    # Merge overlapping intervals with 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

    result.append(new)

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

    return result


def min_meeting_rooms(intervals: list[list[int]]) -> int:
    """Find minimum meeting rooms needed (sweep line)."""
    events = []

    for start, end in intervals:
        events.append((start, 1))   # +1 for start
        events.append((end, -1))    # -1 for end

    # Sort by time, with ends before starts at same time
    events.sort(key=lambda x: (x[0], x[1]))

    max_rooms = 0
    current_rooms = 0

    for _, delta in events:
        current_rooms += delta
        max_rooms = max(max_rooms, current_rooms)

    return max_rooms


def interval_intersection(A: list[list[int]],
                          B: list[list[int]]) -> list[list[int]]:
    """Find intersection of two sorted interval lists."""
    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 interval that ends first
        if A[i][1] < B[j][1]:
            i += 1
        else:
            j += 1

    return result


def can_attend_all(intervals: list[list[int]]) -> bool:
    """Check if a person can attend all meetings."""
    intervals.sort(key=lambda x: x[0])

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

    return True

Recognition Signals

Look for these keywords and patterns in problem descriptions:

intervalsmergeoverlappingmeeting roomsscheduletime slotsrangeinsert intervalnon-overlappingintersection

When to Use

Merging overlapping intervals
Inserting an interval into a sorted list
Finding gaps between intervals
Meeting room scheduling
Finding interval intersections

Common Mistakes

Not sorting first

Trying to process unsorted intervals leads to incorrect results because overlaps aren't detected properly.

Fix:

Always sort intervals by start time before processing:

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

Wrong overlap condition

Using start < last_end instead of start <= last_end misses adjacent intervals that should be merged (like [1,2] and [2,3]).

Fix:

Use <= for touching intervals, < for strict overlap only. Check problem requirements for whether touching counts as overlapping.

Not updating end correctly when merging

Pattern Variations

Merge intervals

Combine all overlapping intervals into non-overlapping intervals.

Examples: Merge Intervals

Insert interval

Insert a new interval into a sorted list, merging with any overlapping intervals.

Examples: Insert Interval

Meeting rooms

Find minimum resources needed for concurrent intervals using sweep line or min-heap.

Examples: Meeting Rooms II, Car Pooling

Interval intersection

Find common regions between two lists of intervals using two pointers.

Examples: Interval List Intersections

Non-overlapping intervals

Find minimum removals to make all intervals non-overlapping. Greedy approach: keep intervals that end earliest.

Examples: Non-overlapping Intervals, Erase Overlap Intervals

Learning Path

2Core Practice0/4

Master the pattern with these representative problems.

Car Pooling

#1094Medium

Insert IntervalOptimal

#57Medium

Maximum Length of Pair ChainOptimal

#646Medium

Merge IntervalsOptimal

#56Medium

Related Patterns

Explore similar techniques:

Two Pointers

Use two pointers to traverse data from different positions, often moving toward or away from each other. This technique transforms O(n²) brute force into O(n) by eliminating redundant comparisons.

Greedy

Make locally optimal choices at each step, hoping to find a global optimum. Greedy algorithms are simple and efficient but only work when the problem has the greedy choice property—local optima lead to global optimum.