Merge Intervals and Overlapping Ranges
An interval is just a range with a start and an end — a meeting from 9 to 10, a sensor reading valid from timestamp 100 to 200, a genomic region from base pair 5000 to 5400. A huge class of real-world problems boils down to asking whether two or more of these ranges overlap, and if so, collapsing them into the smallest set of non-overlapping ranges that covers the same ground. This lesson covers the classic sort-and-sweep technique for merging overlapping intervals, plus the closely related problems of inserting a new interval into an already-merged list and figuring out how many resources (meeting rooms, servers, runway slots) are needed to handle a set of overlapping intervals at once.
Overview: How Merging Intervals Works
Represent each interval as a two-element list or tuple [start, end], and assume (as is standard, and as this lesson does) that end is always greater than or equal to start, with the range inclusive on both ends unless a problem says otherwise. Two intervals [a_start, a_end] and [b_start, b_end] overlap exactly when neither one ends before the other begins — directly, that’s a_start <= b_end and b_start <= a_end. Checking every pair against every other pair costs O(n^2), and there’s a much better way.
The trick: if you first sort the intervals by their start value, then any interval that overlaps the "current" merged range must immediately follow it in the sorted order — you never have to look back or jump around. That turns an all-pairs comparison into a single linear sweep. Walk through the sorted list keeping a "current merged interval." For each next interval, compare its start to the current merged interval’s end:
- If the next interval’s
startis less than or equal to the current merged interval’send, they overlap (or touch) — extend the current merged interval’sendtomax(current_end, next_end)and keep going. - If it’s strictly greater, the current merged interval is finished — push it to the result and start a new "current" interval.
Picture three meetings: [1, 3], [2, 6], and [8, 10]. Sorted by start they’re already in order. The current interval starts as [1, 3]. The next one, [2, 6], starts at 2, which is <= 3, so it overlaps — the current interval grows to [1, 6]. The next one, [8, 10], starts at 8, greater than 6, so it doesn’t overlap — [1, 6] is finalized and [8, 10] becomes the new current interval. The final merged result is [[1, 6], [8, 10]]. That’s the whole algorithm; everything else here is a variation on this idea.
Two closely related problems build on the same sorted-sweep idea. Insert Interval asks you to add one new interval into a list that is already sorted and merged, without re-sorting and re-merging everything from scratch — a single O(n) pass does it. Minimum meeting rooms flips the question: instead of merging ranges, it asks how many overlap at the same time, answered with a sweep over separately sorted start and end times.
Time and Space Complexity
The dominant cost in the classic merge is the sort, not the merge pass itself — the linear scan that compares neighbors is O(n) on its own, but you can’t skip the sort, so the whole algorithm inherits the sort’s cost.
| Operation | Time | Space | Why |
|---|---|---|---|
| Merge overlapping intervals (sort + sweep) | O(n log n) |
O(n) |
Sorting n intervals by start dominates; the single pass that merges neighbors is O(n). Python’s list.sort (Timsort) uses up to O(n) auxiliary space, and the output holds up to n intervals. |
| Insert one interval into an already-sorted, already-merged list | O(n) |
O(n) |
No sort needed — one linear pass classifies every existing interval as before, overlapping, or after the new one. Space is the output list. |
| Minimum meeting rooms (two-pointer over sorted starts/ends) | O(n log n) |
O(n) |
Sorting the start times and end times separately dominates; the two-pointer sweep after that is O(n). The two sorted arrays cost O(n) space. |
| Naive pairwise overlap check | O(n^2) |
O(1) extra |
Comparing every interval against every other interval avoids sorting but scales quadratically — avoid this for anything but tiny, fixed-size inputs. |
All of these are measured in n, the number of intervals — not the numeric range the intervals span. An interval like [1, 1000000] costs the same as [1, 2] here, since the algorithm iterates over the list of intervals, never over the numbers inside a range.
Examples
Example 1: Merging a List of Overlapping Meetings
This function sorts by start, then does the single-pass merge described above. It handles an empty input defensively, and it updates the end of the last merged interval in place with max() rather than rebuilding tuples, since Python tuples are immutable and would force a fresh allocation on every merge.
def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
if not intervals:
return []
intervals.sort(key=lambda pair: pair[0])
merged: list[list[int]] = [intervals[0]]
for start, end in intervals[1:]:
last_start, last_end = merged[-1]
if start <= last_end:
merged[-1][1] = max(last_end, end)
else:
merged.append([start, end])
return merged
def main() -> None:
meetings = [[1, 3], [2, 6], [8, 10], [15, 18]]
print(merge_intervals(meetings))
main()Output:
[[1, 6], [8, 10], [15, 18]]Sorting [[1, 3], [2, 6], [8, 10], [15, 18]] by start leaves the order unchanged since it was already sorted. The sweep starts with [1, 3] as the current interval. [2, 6] starts at 2, which is <= 3, so it merges in and the current interval grows to [1, 6]. [8, 10] starts at 8, greater than 6, so [1, 6] is finalized and [8, 10] becomes current. [15, 18] starts at 15, greater than 10, so [8, 10] is finalized too and [15, 18] stands alone. The result, [[1, 6], [8, 10], [15, 18]], is exactly what the script prints.
Example 2: Inserting a New Interval Into an Already-Merged List
Insert Interval is a common variant: you’re handed a list already sorted by start and already merged (no two intervals in it overlap), plus one new interval to fold in. Re-running a full sort-and-merge would work but throws away the fact that the input is already sorted. A single O(n) pass does the job in three phases: copy every interval that ends before the new one starts, absorb every interval that overlaps the new one (growing its bounds), then copy whatever’s left.
def insert_interval(intervals: list[list[int]], new_interval: list[int]) -> list[list[int]]:
result: list[list[int]] = []
start, end = new_interval
i = 0
n = len(intervals)
while i < n and intervals[i][1] < start:
result.append(intervals[i])
i += 1
while i < n and intervals[i][0] <= end:
start = min(start, intervals[i][0])
end = max(end, intervals[i][1])
i += 1
result.append([start, end])
while i < n:
result.append(intervals[i])
i += 1
return result
def main() -> None:
existing = [[1, 3], [6, 9]]
new_range = [2, 5]
print(insert_interval(existing, new_range))
main()Output:
[[1, 5], [6, 9]]With existing = [[1, 3], [6, 9]] and new_range = [2, 5], the first while loop looks for intervals ending strictly before 2 — [1, 3] ends at 3, not less than 2, so that loop does nothing. The second while loop absorbs every interval whose start is <= 5: [1, 3] qualifies, so start becomes min(2, 1) = 1 and end becomes max(5, 3) = 5, and i advances to 1. [6, 9] starts at 6, not <= 5, so the loop stops. The merged new interval [1, 5] is appended, then the final loop copies the untouched remainder, [6, 9]. The result is [[1, 5], [6, 9]].
Example 3: Minimum Number of Meeting Rooms
A different question entirely: given a set of overlapping meetings, how many rooms do you need so no two meetings scheduled in the same room overlap? Merging won’t answer this — you need the maximum number of intervals simultaneously active. The standard trick sorts start times and end times separately, then sweeps through: every start needs a room, every end frees one. Track how many rooms are in use and record the peak.
def min_meeting_rooms(intervals: list[list[int]]) -> int:
if not intervals:
return 0
starts = sorted(start for start, end in intervals)
ends = sorted(end for start, end in intervals)
rooms_needed = 0
max_rooms = 0
start_pointer = 0
end_pointer = 0
while start_pointer < len(intervals):
if starts[start_pointer] < ends[end_pointer]:
rooms_needed += 1
start_pointer += 1
max_rooms = max(max_rooms, rooms_needed)
else:
rooms_needed -= 1
end_pointer += 1
return max_rooms
def main() -> None:
meetings = [[0, 30], [5, 10], [15, 20]]
print(min_meeting_rooms(meetings))
main()Output:
2For [[0, 30], [5, 10], [15, 20]], the sorted starts are [0, 5, 15] and the sorted ends are [10, 20, 30]. At start time 0, rooms_needed becomes 1 (0 < 10, the earliest end so far), and max_rooms becomes 1. At start time 5, rooms_needed becomes 2 (5 < 10 still) and max_rooms becomes 2. At start time 15, the earliest unconsumed end (10) is not greater than 15, so a room frees up first (rooms_needed drops to 1, end_pointer advances to 20); the loop re-checks and finds 15 < 20, so a room is taken again (rooms_needed back to 2). The final max_rooms, 2, is the answer.
How It Works Step by Step
Trace the sort-and-sweep merge on [[1, 4], [2, 5], [7, 9], [8, 10]] one interval at a time. The list is already sorted by start, so the sweep begins immediately.
| Step | Interval being processed | Comparison | Merged list after this step |
|---|---|---|---|
| 0 (seed) | [1, 4] |
first interval becomes the initial current interval | [[1, 4]] |
| 1 | [2, 5] |
2 <= 4 → overlaps → extend end to max(4, 5) = 5 |
[[1, 5]] |
| 2 | [7, 9] |
7 <= 5? No → does not overlap → start new current interval |
[[1, 5], [7, 9]] |
| 3 | [8, 10] |
8 <= 9 → overlaps → extend end to max(9, 10) = 10 |
[[1, 5], [7, 10]] |
The final answer, [[1, 5], [7, 10]], only ever looked at each interval once, and only ever compared it against the single most-recently-finalized interval — never against every interval seen so far. That’s the payoff of sorting first: it guarantees that once interval k stops overlapping the current merged range, nothing later in sorted order can overlap it either, so you never need to backtrack.
Common Mistakes
Mistake 1: Forgetting to Sort by Start Before Merging
The single-pass merge only works because sorting guarantees that once an interval stops overlapping the current one, nothing later in the list can overlap it either. Skip the sort — maybe because the input "looked" sorted in a test case — and the algorithm silently produces garbage instead of raising an error.
def merge_intervals_buggy(intervals: list[list[int]]) -> list[list[int]]:
merged: list[list[int]] = [intervals[0]]
for start, end in intervals[1:]:
last_start, last_end = merged[-1]
if start <= last_end:
merged[-1][1] = max(last_end, end)
else:
merged.append([start, end])
return merged
unsorted_meetings = [[5, 10], [1, 3], [6, 8]]
print(merge_intervals_buggy(unsorted_meetings))
# Prints [[5, 10]] -- wrong! [1, 3] does not overlap [5, 10] at all.Because the intervals were never sorted, the first interval, [5, 10], becomes the seed. [1, 3] is checked next: its start, 1, is <= 10, so the code thinks it overlaps and swallows it into [5, 10] — even though [1, 3] and [5, 10] don’t actually touch. The bug doesn’t crash; it just returns a wrong answer that looks plausible. The fix is one line: sort by start before the loop.
def merge_intervals_fixed(intervals: list[list[int]]) -> list[list[int]]:
intervals.sort(key=lambda pair: pair[0])
merged: list[list[int]] = [intervals[0]]
for start, end in intervals[1:]:
last_start, last_end = merged[-1]
if start <= last_end:
merged[-1][1] = max(last_end, end)
else:
merged.append([start, end])
return merged
unsorted_meetings = [[5, 10], [1, 3], [6, 8]]
print(merge_intervals_fixed(unsorted_meetings))Output:
[[1, 3], [5, 10]]With the sort in place, the intervals are processed in the order [1, 3], [5, 10], [6, 8]. [5, 10] doesn’t overlap [1, 3] (5 > 3), so it starts a new current interval; [6, 8] does overlap [5, 10] (6 <= 10), merging in without changing the end (max(10, 8) = 10). The correct result is [[1, 3], [5, 10]].
Mistake 2: A Mutable Default Argument for the Accumulator
It’s tempting to give the "merged so far" list a default value so callers don’t have to pass an empty list explicitly. In Python, a mutable default argument like merged: list = [] is created exactly once, when the function is defined — not once per call. Every call that relies on the default shares the very same list object.
def merge_intervals_with_default(intervals: list[list[int]], merged: list[list[int]] = []) -> list[list[int]]:
intervals.sort(key=lambda pair: pair[0])
for start, end in intervals:
if merged and start <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
return merged
print(merge_intervals_with_default([[1, 3], [2, 6]]))
print(merge_intervals_with_default([[8, 10], [9, 12]]))The first call, on [[1, 3], [2, 6]], correctly prints [[1, 6]] — but it does so by appending directly into the shared default list. The second call, on the unrelated [[8, 10], [9, 12]], still finds that shared list non-empty (it still holds [1, 6] from the first call), so instead of the expected [[8, 12]] it prints [[1, 6], [8, 12]] — silently contaminated by a previous call. This is one of Python’s most notorious gotchas, and interval code with an "accumulator" parameter is exactly the shape that invites it. The fix is the standard idiom: default to None, and create a fresh list inside the function body.
def merge_intervals_safe(intervals: list[list[int]], merged: list[list[int]] | None = None) -> list[list[int]]:
if merged is None:
merged = []
intervals.sort(key=lambda pair: pair[0])
for start, end in intervals:
if merged and start <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
return merged
print(merge_intervals_safe([[1, 3], [2, 6]]))
print(merge_intervals_safe([[8, 10], [9, 12]]))Output:
[[1, 6]]
[[8, 12]]Now each call gets its own fresh merged list when the caller doesn’t supply one, so the two calls no longer interfere with each other.
Mistake 3: Guessing Wrong About Touching Intervals
Whether two intervals that touch at a single point — like [1, 4] and [4, 6] — should merge depends entirely on what the numbers represent, and it’s easy to pick the wrong comparison operator without noticing. Using a strict < instead of <= treats touching intervals as non-overlapping:
def merge_intervals_strict(intervals: list[list[int]]) -> list[list[int]]:
intervals.sort(key=lambda pair: pair[0])
merged: list[list[int]] = [intervals[0]]
for start, end in intervals[1:]:
last_start, last_end = merged[-1]
if start < last_end:
merged[-1][1] = max(last_end, end)
else:
merged.append([start, end])
return merged
back_to_back_meetings = [[1, 4], [4, 6]]
print(merge_intervals_strict(back_to_back_meetings))
# Prints [[1, 4], [4, 6]] -- these stay separate even though they touch exactly at 4.Output:
[[1, 4], [4, 6]]If these represent back-to-back calendar meetings that should read as one continuous busy block, this is wrong — the reader expects [[1, 6]]. Switching the comparison to <= treats a shared boundary as an overlap:
def merge_intervals_inclusive(intervals: list[list[int]]) -> list[list[int]]:
intervals.sort(key=lambda pair: pair[0])
merged: list[list[int]] = [intervals[0]]
for start, end in intervals[1:]:
last_start, last_end = merged[-1]
if start <= last_end:
merged[-1][1] = max(last_end, end)
else:
merged.append([start, end])
return merged
back_to_back_meetings = [[1, 4], [4, 6]]
print(merge_intervals_inclusive(back_to_back_meetings))Output:
[[1, 6]]Neither operator is "more correct" in the abstract — always check the problem statement (or ask, in an interview) whether touching counts as overlapping before writing the comparison.
Best Practices
- Always sort before a single-pass merge — sort by
startfor merging/insertion, but sort byendinstead for greedy interval-scheduling problems like picking the maximum number of non-overlapping intervals. - Decide the touching-boundary rule (
<vs<=) from the problem statement up front, and apply it consistently — it’s one of the most common sources of off-by-one bugs in interval problems. - For "insert one interval into an already-sorted, already-merged list," don’t re-sort and re-merge everything — that throws away information you already have, when a linear
O(n)three-phase scan suffices. - For "how many resources are needed at once" problems (meeting rooms, overlapping bookings, max concurrent users), sweep separately sorted start and end arrays, or use a min-heap of end times — the question is about peak concurrency, not about producing a merged list.
- Never default a list or dict parameter to a mutable literal (
def f(x, acc=[])) — default toNoneand initialize inside the function body. - Mutate the current merged interval’s end with
max()in place (as a list) rather than rebuilding immutable tuples on every merge, to avoid unnecessary allocations in the hot loop. - Remember the complexity is measured in the number of intervals, not the size of the numeric range they cover — merging
[1, 1000000]with[500000, 2000000]is exactly as cheap as merging[1, 2]with[2, 3].
Practice Exercises
- Non-overlapping intervals: Given a list of intervals, find the minimum number you’d need to remove so none of the remaining intervals overlap. Hint: sort by
end, notstart, and greedily keep whichever interval finishes earliest whenever two conflict — this is a different sort key than the merge algorithm in this lesson, and it matters. - Intersection of two interval lists: You’re given two lists of intervals, each already sorted and each internally non-overlapping (e.g., two people’s separate busy schedules). Find every range where both schedules overlap. Hint: use two pointers, one per list, computing the overlap between the two current intervals (if any) before advancing whichever interval ends first.
- Can attend all meetings: Given an unsorted list of meeting intervals, determine whether a single person could attend every one of them (return
TrueorFalse) without producing a merged list at all. For[[0, 30], [5, 10], [15, 20]]the answer isFalse, since the first meeting overlaps both of the others. Hint: sort, then check only adjacent pairs — you don’t need the full merge logic.
Summary
- Two intervals
[a_start, a_end]and[b_start, b_end]overlap whena_start <= b_end and b_start <= a_end; whether a shared boundary counts as overlapping depends on the problem. - Sorting intervals by
startturns anO(n^2)all-pairs comparison into a singleO(n)linear sweep — the sort itself, atO(n log n), dominates the total runtime of the classic merge. - Inserting one new interval into an already-sorted, already-merged list only needs a single
O(n)pass — don’t re-sort and re-merge from scratch. - "How many resources are needed at once" (minimum meeting rooms) is a different question from merging, answered by sweeping separately sorted start and end times in
O(n log n). - Never use a mutable default argument (
acc=[]) for an accumulator parameter — it’s shared across every call that doesn’t override it, and it will silently leak state between calls. - Space complexity for these techniques is
O(n), dominated by the output list (and, for sorting, Python’s Timsort auxiliary space) — none of these techniques needs more than linear extra memory.
