Quick Reference O(n log n) / O(n)

int[][] mergeIntervals(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    List<int[]> merged = new ArrayList<>();
    merged.add(intervals[0]);
    for (int i = 1; i < intervals.length; i++) {
        int[] last = merged.get(merged.size() - 1);
        if (intervals[i][0] <= last[1]) {
            last[1] = Math.max(last[1], intervals[i][1]);
        } else {
            merged.add(intervals[i]);
        }
    }
    return merged.toArray(new int[0][]);
}

func mergeIntervals(intervals [][]int) [][]int {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })
    merged := [][]int{intervals[0]}
    for _, iv := range intervals[1:] {
        last := merged[len(merged)-1]
        if iv[0] <= last[1] {
            last[1] = max(last[1], iv[1])
        } else {
            merged = append(merged, iv)
        }
    }
    return merged
}

def merge_intervals(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

fn merge_intervals(intervals: &mut Vec<[i32; 2]>) -> Vec<[i32; 2]> {
    intervals.sort_by_key(|iv| iv[0]);
    let mut merged = vec![intervals[0]];
    for iv in &intervals[1..] {
        let last = merged.last_mut().unwrap();
        if iv[0] <= last[1] {
            last[1] = last[1].max(iv[1]);
        } else {
            merged.push(*iv);
        }
    }
    merged
}

function mergeIntervals(intervals: number[][]): number[][] {
    intervals.sort((a, b) => a[0] - b[0]);
    const merged = [intervals[0]];
    for (const [start, end] of intervals.slice(1)) {
        const last = merged[merged.length - 1];
        if (start <= last[1]) {
            last[1] = Math.max(last[1], end);
        } else {
            merged.push([start, end]);
        }
    }
    return merged;
}

Use when

Merge overlapping intervals
Insert interval into sorted list
Find gaps between intervals
Meeting rooms / minimum platforms

Watch out

Forgetting to sort first
Wrong merge condition (< vs <=)
Not updating end with max(prev.end, curr.end)

Pattern

Overlapping
Intervals

Merge, insert, and manipulate intervals by sorting and scanning.

Step 01

What Is This Pattern?

The Overlapping Intervals pattern handles problems involving ranges defined by a start and end point. The core technique: sort intervals by start time, then scan through them, checking if the current interval overlaps with the previous one.

The Core Idea

Sort by start time. For each interval, compare its start with the previous interval's end. If they overlap, merge them by extending the end. If they do not overlap, start a new group.

Unsorted

[[1,3],[2,6],[8,10]]

→

Sort + Scan

overlap?

→

Merged

[[1,6],[8,10]]

Visual: Timeline Merge

Overlapping bars on a timeline get merged into wider bars:

Before:

[1, 3]

[2, 6]

[8, 10]

↓ merge ↓

After:

[1, 6]

[8, 10]

💡

Why sort by start time? After sorting, you only need to compare adjacent intervals. If interval B starts after interval A ends, then no later interval can overlap with A either (since all later intervals have even larger start times). This single pass after sorting is what makes the pattern O(n log n).

Step 02

When to Use It

Look for these signals in the problem statement. Any mention of ranges, intervals, or scheduling strongly suggests this pattern:

"merge overlapping intervals" "insert interval" "meeting rooms" "minimum platforms" "start/end ranges" "non-overlapping" "schedule conflicts"

Overlap Condition

Two intervals [a, b] and [c, d] (sorted so a ≤ c) overlap when:

c ≤ b

Second interval starts before (or at) where the first one ends. They overlap.

c > b

Second interval starts after the first one ends. No overlap — start a new group.

⚡

The sorting step is critical. Without sorting, you would need to compare every pair of intervals (O(n^2)). After sorting by start time, a single linear scan suffices because the sorted order guarantees that once an interval does not overlap, no future interval will overlap with the current merged group either.

Step 03

Merge Intervals

The most classic interval problem. Sort by start, then scan through, merging any overlapping intervals by extending the end of the current merged interval.

Algorithm Walkthrough

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

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

2. Start with [1,3]. Merged: [[1,3]]

3. [2,6]: start 2 ≤ prev end 3 → overlap! Extend to [1,6]. Merged: [[1,6]]

4. [8,10]: start 8 > prev end 6 → no overlap. Add new. Merged: [[1,6],[8,10]]

5. [15,18]: start 15 > prev end 10 → no overlap. Merged: [[1,6],[8,10],[15,18]]

Full Code — Merge Intervals

// LeetCode #56 — Merge Intervals
public int[][] merge(int[][] intervals) {
    // Step 1: Sort by start time
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

    List<int[]> merged = new ArrayList<>();

    for (int[] interval : intervals) {
        // No overlap: start a new interval
        if (merged.isEmpty()
            || merged.get(merged.size() - 1)[1] < interval[0]) {
            merged.add(interval);
        } else {
            // Overlap: extend the end
            merged.get(merged.size() - 1)[1] =
                Math.max(
                    merged.get(merged.size() - 1)[1],
                    interval[1]
                );
        }
    }

    return merged.toArray(new int[merged.size()][]);
}

// LeetCode #56 — Merge Intervals
func merge(intervals [][]int) [][]int {
    // Step 1: Sort by start time
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })

    merged := [][]int{}

    for _, interval := range intervals {
        n := len(merged)
        // No overlap: start a new interval
        if n == 0 || merged[n-1][1] < interval[0] {
            merged = append(merged, interval)
        } else {
            // Overlap: extend the end
            if interval[1] > merged[n-1][1] {
                merged[n-1][1] = interval[1]
            }
        }
    }

    return merged
}

# LeetCode #56 — Merge Intervals
def merge(intervals: list[list[int]]) -> list[list[int]]:
    # Step 1: Sort by start time
    intervals.sort(key=lambda x: x[0])

    merged: list[list[int]] = []

    for interval in intervals:
        # No overlap: start a new interval
        if not merged or merged[-1][1] < interval[0]:
            merged.append(interval)
        else:
            # Overlap: extend the end
            merged[-1][1] = max(merged[-1][1], interval[1])

    return merged

// LeetCode #56 — Merge Intervals
impl Solution {
    pub fn merge(intervals: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        // Step 1: Sort by start time
        let mut intervals = intervals;
        intervals.sort_by(|a, b| a[0].cmp(&b[0]));

        let mut merged: Vec<Vec<i32>> = Vec::new();

        for interval in intervals {
            let n = merged.len();
            // No overlap: start a new interval
            if n == 0 || merged[n - 1][1] < interval[0] {
                merged.push(interval);
            } else {
                // Overlap: extend the end
                let last = &mut merged[n - 1];
                last[1] = last[1].max(interval[1]);
            }
        }

        merged
    }
}

// LeetCode #56 — Merge Intervals
function merge(intervals: number[][]): number[][] {
    // Step 1: Sort by start time
    intervals.sort((a, b) => a[0] - b[0]);

    const merged: number[][] = [];

    for (const interval of intervals) {
        // No overlap: start a new interval
        if (merged.length === 0
            || merged[merged.length - 1][1] < interval[0]) {
            merged.push(interval);
        } else {
            // Overlap: extend the end
            merged[merged.length - 1][1] =
                Math.max(
                    merged[merged.length - 1][1],
                    interval[1]
                );
        }
    }

    return merged;
}

🎯

Why Math.max for the end? Consider [1,10] and [2,5]. The second interval is completely contained within the first. We need max(10, 5) = 10 to keep the larger end. Without max, we would incorrectly shrink the interval.

Step 04

Insert Interval

Given a sorted, non-overlapping list of intervals, insert a new interval and merge if necessary. The algorithm has three clean phases:

Three Phases

Phase 1: Add all intervals that end before newInterval starts

These are completely to the left. No overlap possible. Add them as-is.

Phase 2: Merge all intervals that overlap with newInterval

Extend newInterval's start to min, end to max of all overlapping intervals.

Phase 3: Add all intervals that start after newInterval ends

These are completely to the right. No overlap possible. Add them as-is.

Full Code — Insert Interval

// LeetCode #57 — Insert Interval
public int[][] insert(int[][] intervals, int[] newInterval) {
    List<int[]> result = new ArrayList<>();
    int i = 0, n = intervals.length;

    // Phase 1: Add all intervals ending before newInterval
    while (i < n && intervals[i][1] < newInterval[0]) {
        result.add(intervals[i++]);
    }

    // Phase 2: Merge overlapping intervals
    while (i < n && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
        newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
        i++;
    }
    result.add(newInterval);

    // Phase 3: Add remaining intervals
    while (i < n) {
        result.add(intervals[i++]);
    }

    return result.toArray(new int[result.size()][]);
}

// LeetCode #57 — Insert Interval
func insert(intervals [][]int, newInterval []int) [][]int {
    result := [][]int{}
    i, n := 0, len(intervals)

    // Phase 1: Add all intervals ending before newInterval
    for i < n && intervals[i][1] < newInterval[0] {
        result = append(result, intervals[i])
        i++
    }

    // Phase 2: Merge overlapping intervals
    for i < n && intervals[i][0] <= newInterval[1] {
        if intervals[i][0] < newInterval[0] {
            newInterval[0] = intervals[i][0]
        }
        if intervals[i][1] > newInterval[1] {
            newInterval[1] = intervals[i][1]
        }
        i++
    }
    result = append(result, newInterval)

    // Phase 3: Add remaining intervals
    for i < n {
        result = append(result, intervals[i])
        i++
    }

    return result
}

# LeetCode #57 — Insert Interval
def insert(intervals: list[list[int]], new_interval: list[int]) -> list[list[int]]:
    result: list[list[int]] = []
    i, n = 0, len(intervals)

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

    # Phase 2: Merge 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

// LeetCode #57 — Insert Interval
impl Solution {
    pub fn insert(intervals: Vec<Vec<i32>>, mut new_interval: Vec<i32>) -> Vec<Vec<i32>> {
        let mut result: Vec<Vec<i32>> = Vec::new();
        let n = intervals.len();
        let mut i = 0;

        // Phase 1: Add all intervals ending before new_interval
        while i < n && intervals[i][1] < new_interval[0] {
            result.push(intervals[i].clone());
            i += 1;
        }

        // Phase 2: Merge overlapping intervals
        while i < n && intervals[i][0] <= new_interval[1] {
            new_interval[0] = new_interval[0].min(intervals[i][0]);
            new_interval[1] = new_interval[1].max(intervals[i][1]);
            i += 1;
        }
        result.push(new_interval);

        // Phase 3: Add remaining intervals
        while i < n {
            result.push(intervals[i].clone());
            i += 1;
        }

        result
    }
}

// LeetCode #57 — Insert Interval
function insert(intervals: number[][], newInterval: number[]): number[][] {
    const result: number[][] = [];
    let i = 0;
    const n = intervals.length;

    // Phase 1: Add all intervals ending before newInterval
    while (i < n && intervals[i][1] < newInterval[0]) {
        result.push(intervals[i++]);
    }

    // Phase 2: Merge overlapping intervals
    while (i < n && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
        newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
        i++;
    }
    result.push(newInterval);

    // Phase 3: Add remaining intervals
    while (i < n) {
        result.push(intervals[i++]);
    }

    return result;
}

Example Walkthrough

intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]

Phase 1: [1,2] ends before 4 → add as-is. Result: [[1,2]]

Phase 2: [3,5] overlaps [4,8] → merge to [3,8]

Phase 2: [6,7] overlaps [3,8] → still [3,8]

Phase 2: [8,10] overlaps [3,8] → merge to [3,10]. Add [3,10].

Phase 3: [12,16] starts after 10 → add as-is. Result: [[1,2],[3,10],[12,16]]

💡

No sorting needed! Unlike Merge Intervals, the input is already sorted and non-overlapping. The three-phase approach runs in O(n) time, which is optimal since we must examine every interval at least once.

Step 05

Common Problems

These are the classic Overlapping Intervals problems you should practice:

#56 Merge Intervals Medium
#57 Insert Interval Medium
#252 Meeting Rooms Easy
#253 Meeting Rooms II Medium
#435 Non-overlapping Intervals Medium

📝

Study order: Start with #56 (core merge pattern), then #57 (insert variant), then #252 (simple overlap check), then #253 (uses a min-heap for concurrent rooms), and finally #435 (greedy removal of minimum intervals).

Step 06

Interactive Demo

Enter intervals as pairs (e.g., "1,3 2,6 8,10 15,18"). Watch them get sorted and merged step by step on a timeline.

⚙ Interval Merge Visualizer

Intervals (pairs separated by spaces)

Step 07

Complexity Analysis

Time

O(n log n)

Space

O(n)

The dominant cost is sorting the intervals: O(n log n). The merge scan itself is just O(n). We need O(n) space for the output list (in the worst case, no intervals overlap and we store all n).

Breakdown by Variant

MERGE INTERVALS

O(n log n)

Sort + linear scan

INSERT INTERVAL

O(n)

Already sorted, single scan

⚡

Can we do better than O(n log n)? Not in general. To detect all overlaps, we need sorted order. However, if the input is already sorted (as in Insert Interval), we skip the sort and achieve O(n). For Meeting Rooms II, a min-heap adds O(n log n) for heap operations, matching the sort cost.

OverlappingIntervals