Pattern 13 · Intervals
Merge Intervals
Anything with a start and an end — meetings, ranges, balloons — yields to the same move: sort by start, then sweep, comparing each interval only against the last one kept.
time O(n log n)space O(n)key move sort by startpractice 10 problems
01 core concept
Sort, then handle overlaps one at a time
Unsorted intervals can overlap anywhere, so every pair might interact — O(n²) chaos. Sorted by start, an interval can only overlap the one merged region growing right before it. One comparison per interval, and the whole problem falls into a single pass.
Input intervals: [1,3] [2,6] [8,10] [15,18]
Number line visualization:
1---3
2-------6
8--10
15--18
|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
Merged result: [1,6] [8,10] [15,18]
1-----------6
8--10
15--18
step 1 / 8walkthrough — merge [[1,4],[0,2],[3,5],[7,9],[6,8]]
result []
The raw input — out of order. Merging requires sorted input: unsorted, [0,2] could hide behind [7,9] and we'd miss the overlap. Step one is always the sort.
02 overlap geometry
The four ways two intervals can meet
For [a, b] and [c, d] with a ≤ c (guaranteed after sorting),
everything reduces to comparing b and c:
OVERLAP (b >= c): NO OVERLAP (b < c):
a---------b a----b
c---------d c----d
gap
Merged: [a, max(b, d)] Keep both separate
CONTAINMENT (b >= d): TOUCHING (b == c):
a-----------------b a----b
c-----d c----d
Merged: [a, b] Merged: [a, d]
(inner absorbed) (considered overlapping)
The formal overlap test
With intervals sorted by start time, an overlap exists exactly when
current.start <= previous.end. Note max(b, d) on merge —
containment means the earlier interval can already extend past the new one.
Five operations cover the whole pattern:
- Merge overlapping intervals.
- Insert a new interval into an existing sorted list.
- Intersect two lists of intervals.
- Find gaps between intervals (free time).
- Count overlaps (meeting rooms, max concurrent).
03 recognition
When to reach for it
| signal in problem | likely approach |
|---|---|
| "merge overlapping intervals" | Sort + merge |
| "insert interval" | Find overlap range, merge |
| "minimum meeting rooms" | Sort + min heap of end times |
| "can attend all meetings?" | Sort + check any overlap |
| "free time between meetings" | Merge, then find gaps |
| "interval intersection" | Two pointers on sorted lists |
| "minimum intervals to remove" | Greedy, keep non-overlapping |
| problem has "start" and "end" fields | Interval technique |
When sort-by-start + merge is NOT the move
Counting concurrent overlaps (meeting rooms) — merging destroys the count;
use a min heap of end times or a sweep line instead.
Max non-overlapping / min removals — that's greedy scheduling: sort by
end time, not start (see Pattern 10).
04 the playbook
One skeleton, six problems
1. SORT by start time (or end time for scheduling)
2. ITERATE through intervals sequentially
3. COMPARE current interval with last in result:
--> overlap? MERGE (extend end time)
--> no overlap? ADD current to result
4. For counting concurrent: use a min heap of ends,
or a sweep line with events
T1Merge Intervals — LC 56
merge_intervals.py — LC 56python
def merge(intervals):
intervals.sort(key=lambda x: x[0]) # sort by start
merged = [intervals[0]]
for start, end in intervals[1:]:
if start <= merged[-1][1]: # overlap with last merged
merged[-1][1] = max(merged[-1][1], end) # extend end
else:
merged.append([start, end]) # no overlap, add new
return mergedT2Insert Interval — LC 57
The list is already sorted, so no re-sort — a three-phase scan: everything strictly before, everything overlapping (absorbed into the new interval), everything after. O(n).
insert_interval.py — LC 57python
def insert(intervals, newInterval):
result = []
i = 0
n = len(intervals)
# 1. Add all intervals that come BEFORE newInterval
while i < n and intervals[i][1] < newInterval[0]:
result.append(intervals[i])
i += 1
# 2. Merge all overlapping intervals with newInterval
while i < n and intervals[i][0] <= newInterval[1]:
newInterval[0] = min(newInterval[0], intervals[i][0])
newInterval[1] = max(newInterval[1], intervals[i][1])
i += 1
result.append(newInterval)
# 3. Add all intervals that come AFTER
while i < n:
result.append(intervals[i])
i += 1
return resultExisting: [1,2] [3,5] [6,7] [8,10] [12,16]
Insert: [4,8]
Before [4,8]: [1,2] (end 2 < start 4)
Overlap: [3,5] [6,7] [8,10] (start <= 8 and end >= 4)
Merged: [3,10] (min starts, max ends)
After: [12,16]
Result: [1,2] [3,10] [12,16]
T3Non-overlapping Intervals — LC 435
Minimum removals so nothing overlaps. This one sorts by end time:
always keeping the interval that ends earliest leaves maximum room, so it maximizes the
kept set — removals are just n - kept.
non_overlapping.py — LC 435python
def eraseOverlapIntervals(intervals):
"""Minimum intervals to remove so none overlap."""
intervals.sort(key=lambda x: x[1]) # sort by END time (greedy)
count = 0
prev_end = float('-inf')
for start, end in intervals:
if start >= prev_end:
# No overlap, keep this interval
prev_end = end
else:
# Overlap, remove this one (it ends later)
count += 1
return count[[1,3],[2,4],[3,5]] sorted by end: [[1,3],[2,4],[3,5]]
[1,3]: no overlap --> keep, prev_end = 3
[2,4]: 2 < 3 --> overlap --> remove, count = 1
[3,5]: 3 >= 3 --> no overlap --> keep, prev_end = 5
Answer: 1 removal
T4Meeting Rooms — LC 252
meeting_rooms.py — LC 252python
def canAttendMeetings(intervals):
"""Can a person attend all meetings (no overlaps)?"""
intervals.sort(key=lambda x: x[0])
for i in range(1, len(intervals)):
if intervals[i][0] < intervals[i - 1][1]:
return False # overlap found
return True
# [0,30] [5,10] [15,20] -> sorted: [0,30],[5,10],[15,20]
# 5 < 30? YES -> return False (can't attend all)T5Meeting Rooms II — LC 253
Minimum rooms = maximum concurrent meetings. Keep a min heap of end times, one entry per room in use. The root is the room that frees up first — reuse it if it's done before the next meeting starts.
step 1 / 6walkthrough — meeting rooms II: [[0,30],[5,10],[15,20]]
heap (end times) []
rooms 0
Meetings sorted by start. The min heap holds one end time per room in use — its root is the room that frees up first.
meeting_rooms_ii.py — LC 253python
import heapq
def minMeetingRooms(intervals):
"""Minimum number of meeting rooms required."""
intervals.sort(key=lambda x: x[0]) # sort by start
heap = [] # min heap of end times (rooms in use)
for start, end in intervals:
# If earliest ending room is free, reuse it
if heap and heap[0] <= start:
heapq.heappop(heap)
# Assign a room (new or reused)
heapq.heappush(heap, end)
return len(heap) # heap size = rooms neededThe alternative — a sweep line: turn every interval into +1/−1 events and track the running count.
meeting_rooms_ii_sweep.pypython
def minMeetingRooms_sweep(intervals):
events = []
for start, end in intervals:
events.append((start, 1)) # meeting starts: +1 room
events.append((end, -1)) # meeting ends: -1 room
events.sort() # sort by time, then by type (-1 before +1 at same time)
max_rooms = 0
current_rooms = 0
for time, delta in events:
current_rooms += delta
max_rooms = max(max_rooms, current_rooms)
return max_roomsTimeline for [[0,30],[5,10],[15,20]]:
Events: (0,+1) (5,+1) (10,-1) (15,+1) (20,-1) (30,-1)
Time: 0 5 10 15 20 30
Rooms: 1 2 1 2 1 0
^ v v
start end end
Max concurrent = 2
T6Interval List Intersections — LC 986
Two already-sorted lists → two pointers. The candidate intersection is
[max(starts), min(ends)]; advance whichever interval ends first
(it can't intersect anything else).
interval_intersections.py — LC 986python
def intervalIntersection(firstList, secondList):
"""Find intersections of two sorted interval lists."""
result = []
i = j = 0
while i < len(firstList) and j < len(secondList):
# Find overlap
start = max(firstList[i][0], secondList[j][0])
end = min(firstList[i][1], secondList[j][1])
if start <= end:
result.append([start, end])
# Advance the pointer with the smaller end
if firstList[i][1] < secondList[j][1]:
i += 1
else:
j += 1
return resultA: [0,2] [5,10] [13,23] [24,25]
B: [1,5] [8,12] [15,24] [25,26]
0--2 5------10 13----------23 24-25
1----5 8-----12 15---------24 25-26
Intersections:
1-2 8-10 15----23 24-24 25-25
Two pointer: advance whichever interval ENDS first
T7Employee Free Time — LC 759
Flatten everyone's schedule, sort, merge — then the gaps between merged blocks are the common free time.
employee_free_time.py — LC 759python
def employeeFreeTime(schedule):
"""Find common free time across all employees."""
# Flatten all intervals and sort
all_intervals = []
for employee in schedule:
for interval in employee:
all_intervals.append(interval)
all_intervals.sort(key=lambda x: x.start)
# Merge all intervals, then find gaps
result = []
prev_end = all_intervals[0].end
for interval in all_intervals[1:]:
if interval.start > prev_end:
result.append(Interval(prev_end, interval.start)) # gap = free time
prev_end = max(prev_end, interval.end)
return resultEmployee 1: [1,3] [6,7]
Employee 2: [2,4]
Employee 3: [2,5] [9,12]
All sorted: [1,3] [2,4] [2,5] [6,7] [9,12]
Merged: [1,5] [6,7] [9,12]
Gaps: [5,6] [7,9]
Free time: [[5,6], [7,9]]
refComplexity reference
| problem | time | space | notes |
|---|---|---|---|
| Merge Intervals | O(n log n) | O(n) | Sort dominates |
| Insert Interval | O(n) | O(n) | Already sorted, single pass |
| Non-overlapping (removals) | O(n log n) | O(1) | Sort by end, greedy |
| Meeting Rooms | O(n log n) | O(1) | Sort + single pass |
| Meeting Rooms II (heap) | O(n log n) | O(n) | Sort + heap operations |
| Meeting Rooms II (sweep) | O(n log n) | O(n) | Sort events |
| Interval Intersections | O(n + m) | O(1)* | Two pointers, already sorted |
| Employee Free Time | O(n log n) | O(n) | Flatten + sort + merge |
* output space not counted.
05 common mistakes
Where intervals go wrong
Mistake 1 — forgetting to sort
The merge algorithm requires sorted input. Always sort by start time first
(or end time for greedy scheduling). On LC 57 the input is pre-sorted — that's the exception, not the rule.
Mistake 2 — > vs ≥ on the overlap check
Do [1,5] and [5,10] overlap? Depends on the problem.
Merging touching intervals: start <= prev_end (inclusive).
Meeting rooms: start < prev_end — back-to-back meetings don't conflict
if one ends exactly as the other starts.
Mistake 3 — mutating the input while iterating
Build a fresh result list instead of splicing intervals in place mid-loop.
Mistake 4 — wrong sort key for greedy variants
Non-overlapping intervals and scheduling problems often need sort by end time,
not start time. Merging needs start. Say which one you're using and why.
Mistake 5 — missing containment and edge cases
Empty input, a single interval, and fully contained intervals like [1,10] holding
[3,5] — this is why the merge extends with max(prev_end, end),
never just end.
10 practice
Practice ladder
In this order — easiest first. Tick each one as you solve it, and re-solve anything that took more than 25 minutes two days later.
10 problems
mediumLC 452
Same shape as non-overlapping — sort by end (Pattern 10).