PATTERN 16 OF 22

Intervals

Interval problems involve ranges [start, end] that may overlap, touch, or be disjoint. Master sort-and-merge, sweep line, and end-sort greedy techniques to efficiently merge, count, insert, and remove intervals.

Time: O(n log n) for single-pass greedy with sort, O(n) for insert into pre-sorted list

Space: O(n) for storing merged result, O(1) additional in greedy selection problems

Learn & Reference

Understanding the Pattern

Intervals Pattern

Interval problems deal with ranges [start, end] — scheduling meetings, merging time slots, or finding overlaps. Nearly every interval problem starts the same way: sort the intervals, then process them with a single scan.

Intervals:  |----|    |------|   |--|
Sorted:     |--|  |----|  |------|  |--|
Merge:      |--|  |--------|       |--|

The key insight: once intervals are sorted, overlapping ranges become adjacent in the array, making them easy to detect and process.

Overlap Detection — The Foundation

Two intervals [a, b] and [c, d] overlap when:

a < d  AND  c < b     (strict — touching doesn't count)
a <= d AND  c <= b     (inclusive — touching counts as overlap)

Which version to use depends on the problem. Read carefully whether touching intervals should be merged or kept separate.

Five Core Techniques

1. Sort + Merge

Pattern: Sort by start time, then sweep left to right merging overlapping intervals.

Input:   [1,3] [2,6] [8,10] [15,18]
Sort:    [1,3] [2,6] [8,10] [15,18]  (already sorted)
Process: [1,3] + [2,6] → overlap (2 ≤ 3) → merge to [1,6]
         [1,6] + [8,10] → no overlap (8 > 6) → new group
         [8,10] + [15,18] → no overlap → new group
Result:  [1,6] [8,10] [15,18]

When to use: "merge all overlapping intervals", "combine ranges"

2. Insert + Merge

Pattern: Insert a new interval into a sorted list. Three phases:

Add all intervals that end before the new one starts
Merge all intervals that overlap with the new one
Add all intervals that start after the new one ends

When to use: "insert interval into sorted list", "add a new range"

3. End-Sort Greedy

Pattern: Sort by end time (not start). Greedily select intervals that finish earliest to maximize non-overlapping selections, or equivalently minimize removals.

Sorted by end:  [1,2] [1,3] [2,3] [3,4]
Select [1,2] → skip [1,3] (overlaps) → select [2,3] → select [3,4]
Kept: 3 intervals, removed: 1

When to use: "minimum intervals to remove", "maximum non-overlapping", "minimum arrows/shots"

4. Sweep Line

Pattern: Create events for starts (+1) and ends (-1). Sort events by time. Sweep through to find maximum concurrent count.

Meetings: [0,30] [5,10] [15,20]
Events:   (0,+1) (5,+1) (10,-1) (15,+1) (20,-1) (30,-1)
Sweep:    0→1, 5→2, 10→1, 15→2, 20→1, 30→0
Max concurrent: 2 → need 2 rooms

Alternative (more efficient): sort starts and ends separately, use two pointers.

When to use: "minimum rooms/resources", "maximum overlapping at any point"

5. Overlap Detection

Pattern: Check if any two intervals overlap, or find all pairs that overlap. Foundation for all other techniques.

[a, b] overlaps [c, d]  ⟺  a < d AND c < b

When to use: "do any meetings conflict?", "find overlapping ranges"

Common Mistakes

Off-by-one with touching intervals — [1,2] and [2,3]: some problems treat this as overlapping (merge), others as non-overlapping (keep separate). Read the problem statement carefully.
Not sorting before processing — Almost every interval problem requires sorting first. Forgetting this leads to wrong answers on unsorted input.
Sorting by the wrong key — Sort by start for merge problems, sort by end for greedy selection problems. Using the wrong key breaks the invariant.
Integer overflow in comparators — In Java, a[0] - b[0] overflows for extreme values. Always use Integer.compare(a[0], b[0]).
Mutating input vs building new array — Some problems expect a new result array; others can modify in-place. Be clear about what you're returning.
Confusing "can touch" with "can overlap" — start <= end (touching counts) vs start < end (strict overlap). One character difference, completely different results.

Template

1# --- Sort + Merge Template ---
2def solve(intervals):
3    intervals.sort()
4    merged = [intervals[0]]
5    for start, end in intervals[1:]:
6        if start <= merged[-1][1]:  # Overlapping
7            merged[-1][1] = max(merged[-1][1], end)
8        else:
9            merged.append([start, end])
10    return merged
11
12# --- Sweep Line Template ---
13def max_concurrent(intervals):
14    starts = sorted(s for s, e in intervals)
15    ends = sorted(e for s, e in intervals)
16    rooms = 0
17    max_rooms = 0
18    s = e = 0
19    while s < len(intervals):
20        if starts[s] < ends[e]:
21            rooms += 1
22            max_rooms = max(max_rooms, rooms)
23            s += 1
24        else:
25            rooms -= 1
26            e += 1
27    return max_rooms

{ }

Syntax Reference

1# --- Sorting intervals ---
2intervals.sort()                        # Sort by start (default tuple sort)
3intervals.sort(key=lambda x: x[1])     # Sort by end
4
5# --- Unpacking ---
6for start, end in intervals:           # Destructure each interval
7
8# --- Building result ---
9merged = [intervals[0]]
10merged.append([start, end])
11merged[-1][1] = max(merged[-1][1], end)  # Extend last interval
12
13# --- Overlap check ---
14# Inclusive: start <= prev_end
15# Strict:   start < prev_end

📋

Common Recipes

1# Recipe 1: Merge Overlapping Intervals
2def merge(intervals):
3    intervals.sort()
4    merged = [intervals[0]]
5    for start, end in intervals[1:]:
6        if start <= merged[-1][1]:
7            merged[-1][1] = max(merged[-1][1], end)
8        else:
9            merged.append([start, end])
10    return merged
11
12# Recipe 2: Sweep Line — Max Concurrent (Meeting Rooms II)
13def min_meeting_rooms(intervals):
14    starts = sorted(s for s, e in intervals)
15    ends = sorted(e for s, e in intervals)
16    rooms = 0
17    max_rooms = 0
18    s = e = 0
19    while s < len(intervals):
20        if starts[s] < ends[e]:
21            rooms += 1
22            max_rooms = max(max_rooms, rooms)
23            s += 1
24        else:
25            rooms -= 1
26            e += 1
27    return max_rooms
28
29# Recipe 3: End-Sort Greedy — Min Arrows / Max Non-overlapping
30def find_min_arrow_shots(points):
31    points.sort(key=lambda x: x[1])
32    arrows = 1
33    arrow_pos = points[0][1]
34    for start, end in points[1:]:
35        if start > arrow_pos:
36            arrows += 1
37            arrow_pos = end
38    return arrows

O(n)

Complexity

Technique	Time	Space	Example
Sort + Merge	O(n log n)	O(n)	Merge Intervals
Insert + Merge	O(n)	O(n)	Insert Interval
End-Sort Greedy	O(n log n)	O(1)	Non-overlapping Intervals
Sweep Line	O(n log n)	O(n)	Meeting Rooms II
End-Sort + Count	O(n log n)	O(1)	Burst Balloons

Watch Out

✗Off-by-one with touching intervals — `[1,2]` and `[2,3]`: some problems treat this as overlapping (merge), others as non-overlapping (keep separate). Read the problem statement carefully.
✗Not sorting before processing — Almost every interval problem requires sorting first. Forgetting this leads to wrong answers on unsorted input.
✗Sorting by the wrong key — Sort by start for merge problems, sort by end for greedy selection problems. Using the wrong key breaks the invariant.
✗Integer overflow in comparators — In Java, `a[0] - b[0]` overflows for extreme values. Always use `Integer.compare(a[0], b[0])`.
✗Mutating input vs building new array — Some problems expect a new result array; others can modify in-place. Be clear about what you're returning.
✗Confusing "can touch" with "can overlap" — `start <= end` (touching counts) vs `start < end` (strict overlap). One character difference, completely different results.

PRACTICE PROBLEMS

Greedy

Dynamic Programming (2D)