2Brute2Best
🔥0

Intervals Pattern: Algorithmic Intuition, Sub-patterns & C++ Guide

Sort intervals (usually by start), then walk once — each new interval only needs to be compared with the last one you kept.

4 sub-patterns · 16 questions

Remember this · Intervals
Trigger
Input is [start, end] pairs; overlap, merge, insert, meeting rooms, free time, minimum removals.
Think
After sorting, do I only ever need to compare against the most recent interval?
Key question
Sort by start or by end — which one makes the greedy choice obvious?
A

What is this pattern?

An interval is a pair [start, end]: a meeting, a train's stay at a station, a balloon, a video clip. Questions ask how they overlap: merge them, count how many are active at once, find the gaps, or pick as few / as many as possible.

Comparing every pair is O(N²). The pattern is: sort first, then walk once. After sorting by start, an interval can only overlap the ones just before it — so you compare it with the last interval you kept and nothing else. That makes the whole thing O(N log N): the sort, plus one O(N) pass.

Two intervals a and b overlap when a.start ≤ b.end and b.start ≤ a.end. Whether touching ends ([1,2] and [2,3]) count as overlapping depends on the problem — decide it before writing the comparison.

Laying strips of tape on a ruler. Sort the strips by where they start and lay them left to right. Each new strip either starts before the tape you've laid so far ends — so it just extends that tape — or it starts after a gap, so you begin a new piece. You never need to look further back than the end of the last piece.

B

See it move

Merge Intervals. Each row is one interval on a timeline 0–15 (closed: [2,6] covers 2 through 6). Blue = being compared now, green = already merged in, purple rows at the bottom = the merged answer so far.

Only the last block can overlapintervals = [[8,10], [1,3], [2,6], [9,12], [4,5], [15,15]]step 1/8
[1,3]
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
[2,6]
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
[4,5]
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
[8,10]
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
[9,12]
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
[15,15]
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
merged
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Sorted by start
[1,3][2,6][4,5][8,10][9,12][15,15]
State
merged
[]
Sorted by start

The input [[8,10], [1,3], [2,6], [9,12], [4,5], [15,15]] is sorted by start first. Now each interval only has to be compared with the last merged block.

Non-overlapping Intervals. Rows are intervals on a timeline 0–11, half-open: [2,4] shades 2 and 3, so touching ends like [3,6] and [6,9] don't clash. Blue = looking at now, green = kept, red = removed.

Keep whoever finishes firstintervals = [[1,11], [2,4], [3,6], [5,7], [8,10], [6,9]]step 1/8
[2,4]
0
1
2
3
4
5
6
7
8
9
10
11
0
1
2
3
4
5
6
7
8
9
10
11
[3,6]
0
1
2
3
4
5
6
7
8
9
10
11
0
1
2
3
4
5
6
7
8
9
10
11
[5,7]
0
1
2
3
4
5
6
7
8
9
10
11
0
1
2
3
4
5
6
7
8
9
10
11
[6,9]
0
1
2
3
4
5
6
7
8
9
10
11
0
1
2
3
4
5
6
7
8
9
10
11
[8,10]
0
1
2
3
4
5
6
7
8
9
10
11
0
1
2
3
4
5
6
7
8
9
10
11
[1,11]
0
1
2
3
4
5
6
7
8
9
10
11
0
1
2
3
4
5
6
7
8
9
10
11
Sorted by end
[2,4][3,6][5,7][6,9][8,10][1,11]
State
last kept end
none
kept
0
Sorted by END

Goal: keep as many intervals as possible with no overlap (touching ends are fine). Sort by end — the one that finishes first leaves the most room for everything after it.

C

How do I recognise it?

  • The input is a list of [start, end] pairs (or start/end arrays, or (position, range) that turns into one).

  • "Merge", "insert", "overlapping", "covered by" another interval.

  • Meetings, calendars, rooms, trains and platforms, passengers in a car: "how many at the same time?"

  • "Free time", "gaps", "days without meetings": the parts no interval covers.

  • "Minimum to remove so none overlap", "fewest arrows", "fewest clips / taps to cover [0, T]".

  • The brute force compares every pair of intervals, or keeps re-merging until nothing changes.

Looks like Intervals, but isn't

Add a value to many ranges, then read the totals
→ Prefix Sum (difference array)

If the coordinates are small, +v at the start and −v after the end, then one prefix sum, beats sorting. Car Pooling here uses exactly that; the interval pattern is for when coordinates are huge or you need the intervals themselves.

Choose intervals to maximise total profit / weight
→ Dynamic Programming + Binary Search

"Sort by end and keep the earliest finisher" only works when every interval is worth the same. With weights (Weighted Job Scheduling), you need DP over intervals sorted by end, with a binary search for the last compatible one.

Each index says how far you can jump
→ Greedy (Jump Game II)

That's the same "extend the farthest reach" walk as Video Stitching — [i, i + nums[i]] is just an interval. If it's given as jumps, think greedy; if it's given as clips or taps, think intervals.

K sorted lists of numbers, find the smallest / merge them
→ K-way Merge (heap)

Several sorted lists of numbers is a heap problem. Several sorted lists of intervals where you need overlaps or gaps is this pattern (Employee Free Time uses both).

Longest subarray / substring with some property
→ Sliding Window

A window is an interval of indices that you choose. In this pattern the intervals are given and you merge, count or pick them.

D

How would I discover it from scratch?

Don't memorise “use intervals”. Ask these questions in order — the pattern falls out.

Compare every pair of intervals (O(N²)), or repeatedly merge any two that overlap until nothing changes (even slower). For "how many at once", check every moment in time.

E

Sub-patterns

Same core idea, different rule for “valid”. Learn them in this order.

01

Merge overlaps

4 questions

Sort by start and build the answer left to right. Each interval either extends the last merged block or starts a new one.

02

Scheduling / meeting rooms

5 questions

Count how many intervals are active at the same moment, or check that a new one doesn't clash. Sweep start and end events in time order, or keep a min-heap of end times.

03

Intersection of two lists

3 questions

Two (or more) sorted lists of intervals. Walk them together with two pointers; the overlap of the current pair is [max start, min end]; advance whichever ends first.

04

Coverage / removal

4 questions

Choose which intervals to keep or use. To fit in as many as possible, sort by end and keep the earliest finisher. To cover a whole range with as few as possible, sort by start and keep extending the farthest reach.

F

Don't mix these up

Sort by start vs Sort by end

Building or merging left to right, sweeping time, covering a range → sort by start. Picking the most intervals that don't clash (or the fewest to remove / arrows) → sort by end.

Merge Intervals (LC 56) vs Non-overlapping Intervals (LC 435)

Merge combines overlapping intervals into one; nothing is thrown away. LC 435 throws away intervals so the rest don't touch, and wants the fewest throws.

Non-overlapping Intervals (LC 435) vs Burst Balloons (LC 452)

Same greedy. In LC 435 [1,2] and [2,3] don't overlap (keep both). In LC 452 they do (one arrow at 2 bursts both). One character: >= vs >.

Meeting Rooms II (LC 253) vs Minimum Platforms (GFG)

Same sweep. A meeting that ends at 10 frees its room for a 10:00 start; a train that departs at 10:00 is still on its platform when another arrives at 10:00. The tie rule flips.

Meeting Rooms II (LC 253) vs Car Pooling (LC 1094)

Both ask about the peak load over time. Car Pooling adds passengers (weights) and its stops are small numbers (≤ 1000), so a difference array over the stops is easiest. Meeting times can be huge → sort the events.

G

Code templates (C++)

Merge overlapping intervals

Compare with res.back() — the merged block — not with the previous input interval. Use max for the new end: the next interval might sit completely inside the current one.

merge-template.cpp
// Merge Intervals: sort by start, then extend the last merged block or start a new one.
vector<vector<int>> merge(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end());        // by start (then end)
    vector<vector<int>> res;
    for (auto& cur : intervals) {
        if (!res.empty() && cur[0] <= res.back()[1])      // overlaps the LAST merged block
            res.back()[1] = max(res.back()[1], cur[1]);   // max: cur may sit inside it
        else
            res.push_back(cur);                           // gap → new block
    }
    return res;
}

Max active at once (sweep)

Sort the starts and the ends separately. At each start, first free every room whose meeting has ended (end ≤ start for meetings; use < if a same-time departure still needs a platform). The answer is the most rooms ever in use.

sweep-template.cpp
// Meeting Rooms II: most meetings running at the same time. Meetings are [start, end).
int minMeetingRooms(vector<vector<int>>& meetings) {
    vector<int> starts, ends;
    for (auto& m : meetings) { starts.push_back(m[0]); ends.push_back(m[1]); }
    sort(starts.begin(), starts.end());
    sort(ends.begin(), ends.end());
    int rooms = 0, best = 0, e = 0;
    for (int s : starts) {
        while (e < (int)ends.size() && ends[e] <= s) { rooms--; e++; }  // free ended rooms first
        rooms++;                                                     // this meeting takes one
        best = max(best, rooms);
    }
    return best;
}

Intersect two sorted lists

The overlap of two intervals is [max(starts), min(ends)], if it isn't empty. Then move past the interval that ends first — it can't overlap anything else in the other list.

two-lists-template.cpp
// Interval List Intersections: both lists sorted and disjoint, intervals closed.
vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) {
    vector<vector<int>> res;
    int i = 0, j = 0;
    while (i < (int)A.size() && j < (int)B.size()) {
        int lo = max(A[i][0], B[j][0]);
        int hi = min(A[i][1], B[j][1]);
        if (lo <= hi) res.push_back({lo, hi});        // non-empty overlap
        if (A[i][1] < B[j][1]) i++;                   // advance whoever ends first
        else j++;
    }
    return res;
}

Keep the earliest finisher

Sort by end. Keep an interval if it starts at or after the last kept end. Kept = most non-overlapping; n − kept = fewest removals. For arrows, change >= to > (touching balloons share an arrow).

earliest-end-template.cpp
// Non-overlapping Intervals: fewest removals = n - most intervals we can keep.
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end(),
         [](const vector<int>& a, const vector<int>& b) { return a[1] < b[1]; });  // by END
    int kept = 0;
    long long lastEnd = LLONG_MIN;
    for (auto& in : intervals) {
        if (in[0] >= lastEnd) {                       // fits after the last kept one
            kept++;
            lastEnd = in[1];                          // earliest finisher leaves most room
        }
    }
    return (int)intervals.size() - kept;
}
Next
Start with Merge overlaps