Intervals Pattern

The Intervals pattern is a vital technique used to solve problems involving ranges of numbers, such as schedules, meeting times, calendar blocks, or IP addresses. The core of this pattern is sorting the intervals (typically by their start times) and then sequentially resolving intersections. Sorting transforms a complex multi-dimensional search space into a simple, linear comparison between adjacent elements.

By ordering the inputs, we can solve most interval problems in $O(N log N)$ time, avoiding $O(N^2)$ brute-force comparisons.

The Core Concept: Merge Intervals

To understand this concept deeply, let's explore Merge Intervals.

Problem Statement: Given an array of intervals where intervals[i] = [start, end], merge all overlapping intervals and return an array of the non-overlapping intervals.

Naive Brute Force — $O(N^2)$

A naive approach is to compare every interval with every other interval to see if they overlap, merging them recursively until no overlapping pairs remain:

def mergeNaive(intervals: list[list[int]]) -> list[list[int]]:
    has_overlap = True
    while has_overlap:
        has_overlap = False
        n = len(intervals)
        for i in range(n):
            for j in range(i + 1, n):
                # Check if intervals[i] and intervals[j] overlap
                s1, e1 = intervals[i]
                s2, e2 = intervals[j]
                if not (e1 < s2 or e2 < s1):
                    # Merge intervals[i] and intervals[j]
                    intervals[i] = [min(s1, s2), max(e1, e2)]
                    intervals.pop(j)
                    has_overlap = True
                    break
            if has_overlap:
                break
    return intervals

This is highly inefficient because it requires multiple scans and comparisons of all elements, leading to a worst-case $O(N^2)$ time complexity.

The Intervals Breakthrough — $O(N log N)$

If we sort the intervals by their start times, we guarantee that for any two intervals $A$ and $B$ , if $A$ comes before $B$ , then $A. ext{start} le B. ext{start}$ . This means we only need to compare consecutive intervals in a single linear scan:

If the next interval's start is less than or equal to the current interval's end, they overlap. We merge them by updating the current interval's end to $max( ext{current.end}, ext{next.end})$ .
If the next interval's start is strictly greater than the current interval's end, they do not overlap. We push the current interval to our output and make the next interval our new reference.

Sorting simplifies overlap detection to a single, linear $O(N)$ sweep.

Step-by-Step Traversal

Let's trace the algorithm on the input intervals: [[1, 10], [2, 5], [6, 8]].

Step 1: Sort by Start Time

We sort the input array by the starting value. In this case, the array is already sorted: [[1, 10], [2, 5], [6, 8]].

SETSort by start time: [[1,10], [2,5], [6,8]]1 / 8

Interval 1

[1, 10]

Interval 2

[2, 5]

Interval 3

[6, 8]

Merged

scroll to zoom · drag to pan

Step 2: Initialize

We initialize our merged results with the first interval, [1, 10].

SETNo overlap. Add [1,10] to the merged result.1 / 6

Interval 1

[1, 10]

Interval 2

[2, 5]

Interval 3

[6, 8]

Merged

[1, 10]

scroll to zoom · drag to pan

Step 3: Process Second Interval

We look at the next interval, [2, 5].

We compare its start time ( $2$ ) with the end time of the last merged interval ( $10$ ).
Since $2 le 10$ , they overlap!

COMPARECompare [2,5] with current merged range [1,10].1 / 5

Interval 1

[1, 10]

Interval 2

[2, 5]

Interval 3

[6, 8]

Merged

[1, 10]

scroll to zoom · drag to pan

We merge them by updating the end time to $max(10, 5) = 10$ . The merged interval remains [1, 10].

MERGEOverlap. Extend [1,10] with [2,5] -> [1,10].1 / 4

Interval 1

[1, 10]

Interval 2

[2, 5]

Interval 3

[6, 8]

Merged

[1, 10]

scroll to zoom · drag to pan

Step 4: Process Third Interval

We look at the next interval, [6, 8].

We compare its start time ( $6$ ) with the end time of the last merged interval ( $10$ ).
Since $6 le 10$ , they overlap!

COMPARECompare [6,8] with current merged range [1,10].1 / 3

Interval 1

[1, 10]

Interval 2

[2, 5]

Interval 3

[6, 8]

Merged

[1, 10]

scroll to zoom · drag to pan

We merge them by updating the end time to $max(10, 8) = 10$ . The merged interval remains [1, 10].

MERGEOverlap. Extend [1,10] with [6,8] -> [1,10].1 / 2

Interval 1

[1, 10]

Interval 2

[2, 5]

Interval 3

[6, 8]

Merged

[1, 10]

scroll to zoom · drag to pan

Step 5: Done

All intervals have been scanned. We return the final merged list: [[1, 10]].

DONEMerged intervals: [[1,10]]1 / 1

Interval 1

[1, 10]

Interval 2

[2, 5]

Interval 3

[6, 8]

Merged

[1, 10]

scroll to zoom · drag to pan

Code Implementation

def merge(intervals: list[list[int]]) -> list[list[int]]:
    if not intervals:
        return []
        
    # Sort intervals by their start times
    intervals.sort(key=lambda x: x[0])
    
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        last_end = merged[-1][1]
        
        # If the current interval overlaps with the last merged interval
        if start <= last_end:
            # Merge by extending the end time
            merged[-1][1] = max(last_end, end)
        else:
            # No overlap, add current interval to the list
            merged.append([start, end])
            
    return merged

Time Complexity: $O(N log N)$ — dominated by sorting the intervals. The linear scan takes $O(N)$ time. Space Complexity: $O(N)$ (or $O(log N)$ ) — for storing the sorted intervals or output results.

Core Variations

1. Insert Interval

Given a set of non-overlapping sorted intervals, insert a new interval and merge if necessary.

Approach: Add the new interval and then run the standard merge algorithm, or insert it in-place in a single $O(N)$ scan by finding its correct position.
Example: Insert Interval.

2. Finding Meeting Rooms (Interval Partitioning)

Find the minimum number of resources (like meeting rooms) needed to accommodate all intervals.

Approach: Sort starts and ends separately or use a min-heap to keep track of the end times of active rooms. If a new meeting starts after the earliest end time, we reuse the room; otherwise, we allocate a new one.
Example: Meeting Rooms II.

3. Maximum Non-Overlapping Intervals

Find the maximum number of intervals you can schedule without any overlaps.

Approach: Sort by end time instead of start time. By choosing the interval that finishes earliest, we leave the maximum possible room for subsequent intervals.
Example: Non-overlapping Intervals.

When Do I Use This?

Check for these conditions:

The input is a list of pairs representing ranges: [start, end], [low, high], [first, last].
You need to combine overlapping ranges, find gaps, insert new ranges, or count intersections.
The problem statement mentions keywords like "meeting rooms", "scheduling", "calendar", "free time", or "overlapping".

If yes, the Intervals pattern is your go-to solution.

Practice Problems

Done	Question	Difficulty
	Can Attend Meetings	Easy
	Insert Interval	Medium
	Non-Overlapping Intervals	Medium
	Merge Intervals	Medium
	Employee Free Time	Hard

Intervals Pattern

The Core Concept: Merge Intervals

Naive Brute Force — O(N2)O(N^2)O(N2)

The Intervals Breakthrough — O(NlogN)O(N log N)O(NlogN)

Step-by-Step Traversal

Step 1: Sort by Start Time

Step 2: Initialize

Step 3: Process Second Interval

Step 4: Process Third Interval

Step 5: Done

Code Implementation

Core Variations

1. Insert Interval

2. Finding Meeting Rooms (Interval Partitioning)

3. Maximum Non-Overlapping Intervals

When Do I Use This?

Practice Problems

Comments

Naive Brute Force — $O(N^2)$

The Intervals Breakthrough — $O(N log N)$