What is the intervals pattern?

Problems whose input is a list of [start, end] ranges are solved by sorting the ranges by one endpoint and sweeping through them once, comparing each range only with what the sweep has kept so far.

Why do interval problems sort first?

After sorting by start, any interval that overlaps the current one must be the last one merged, so one comparison per interval replaces comparing every pair. The sort costs O(n log n) and the sweep O(n).

Should I sort intervals by start or by end?

Sort by start to merge or insert ranges. Sort by end when a greedy choice decides what to keep — the most non-overlapping intervals or the fewest arrows — because the range that finishes first leaves the most room.

Intervals Overview

Master the technique of handling overlapping time ranges.

Medium

10 min

Solve on LeetCode

What is the Interval Technique?

The Intervals pattern is a set of techniques used to handle problems involving ranges of data, such as time intervals [start, end]. The core idea revolves around sorting the intervals based on their start (or end) times to process overlaps efficiently.

The Motivation: Merge Intervals

Consider the classic problem: Given a collection of intervals, merge all overlapping intervals.

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

We need a way to combine [1,3] and [2,6] into [1,6] while leaving others intact.

Attempt 1: Brute Force (Why it fails)

A naive approach would be to compare every interval with every other interval to check for overlaps.

For each interval A, iterate through all other intervals B. If they overlap, merge them. Repeat this process until no merges are possible.

Analysis: This requires repeated passes and searching, so one pass already costs O(N²) comparisons, and every merge can force another pass — O(N³) in the worst case. Switch the figure below to Compare every pair to count them.

Visualizing the Brute Force Approach

Imagine trying to fit puzzle pieces together by randomly picking two pieces and checking if they connect. You might pick [8,10] and [1,3] and see they don't match. Then [15,18] and [2,6]. It's inefficient because you aren't checking in any order.

When should I use Intervals?

Input: A list of ranges or intervals (e.g., [start, end]).
Keywords: "Merge", "Overlapping", "Non-overlapping", "Meeting Rooms", "Schedule", "Burst Balloons".
Goal: Find intersections, unions, or gaps between time slots.

The Intuition: Process of Elimination (Sorting)

If we sort the intervals by their start time, we align them linearly. This means for any interval curr, we only need to compare it with the prev interval to check for overlaps. We effectively turn a 2D search problem into a 1D linear scan.

Interactive Walkthrough

4 INTERVALS

UNSORTED

Intervals · as given

[2,6]

[8,10]

[1,3]

[15,18]

Result · 0

Comparisons

Result

result

Empty

4 intervals, in the order given

Sort by start time: [[1,3], [2,6], [8,10], [15,18]]

Intervals

Legend & Complexity

The interval being read, tagged “reading”

The last merged interval it is compared with, or a pair being compared

Already placed in the result: “added” or “merged”

The final result

Sort then sweep

O(n log n)

Every pair

O(n³)

Space

O(n)

In Sort then sweep mode, the intervals are sorted by start and read once, each compared only with the last merged interval. Switch to Compare every pair to watch the brute force check pairs and restart after every merge. Comparisons counts the work each method does.

Dry Run Table

The motivation's input, [[1,3], [2,6], [8,10], [15,18]], already sorted by start.

Step	Current	Last Merged	Overlap?	Action	Result
Init	-	-	-	Sort by start	`[]`
1	`[1,3]`	-	-	Result empty: add	`[[1,3]]`
2	`[2,6]`	`[1,3]`	Yes (`2 <= 3`)	Extend end to `max(3, 6) = 6`	`[[1,6]]`
3	`[8,10]`	`[1,6]`	No (`8 > 6`)	Add as a new interval	`[[1,6], [8,10]]`
4	`[15,18]`	`[8,10]`	No (`15 > 10`)	Add as a new interval	`[[1,6], [8,10], [15,18]]`

The Solution Template

Most interval problems follow this structure.

Intervals Overview Code

1function solveIntervals(intervals) {
2    if (!intervals.length) return [];
3    // 1. Sort
4    intervals.sort((a,b) => a[0] - b[0]);
5    
6    const result = [];
7    
8    // 2. Iterate
9    for (let interval of intervals) {
10        if (!result.length || interval[0] > result[result.length-1][1]) {
11            result.push(interval);
12        } else {
13            // Overlap logic
14            result[result.length-1][1] = Math.max(result[result.length-1][1], interval[1]);
15        }
16    }
17    return result;
18}

Edge Cases & Common Mistakes

Empty Input: Always check if intervals is empty.
Single Interval: Return as is.
Touching Intervals: Whether [1,2] and [2,3] overlap depends on the problem: Merge Intervals joins them into [1,3], Meeting Rooms lets one meeting start as the other ends, and Non-overlapping Intervals keeps both.
Complete Enclosure: [1,10] fully contains [2,5]. Ensure merge logic handles this (max of ends).

Summary

Sort intervals by start time.
Iterate and compare current.start with previous.end.
Merge or insert based on overlap conditions.

Merge Intervals