Python 3.11+
The examples use the standard Python syntax and containers supported by the browser Judge; the Merge Intervals invariant is independent of a minor Python release.
Verify in Python docs(opens in a new tab)Pattern1 Practice2 Interview
Merge Intervals
Sort intervals and combine overlapping ranges while tracking the current merged endpoint. Learn its decision rule, maintained state, Python cost model, and transfer from a focused drill to a full Interview Problem.
Recognize it when
Consider Merge Intervals when the prompt's constraints and required operations match this shape: Sort intervals and combine overlapping ranges while tracking the current merged endpoint.
On this page · Sort to Make Overlap Local
Checking your account…
Sign in to save your code and progress across devices. The lesson and problem statement remain public.
Merge Intervals Code Labs
Sort to Make Overlap Local
Sorting intervals by start ensures that a new interval can overlap only the last merged interval. A global overlap problem becomes one comparison per interval.
Carry One Merged Interval
If start lies after the current end, emit a new block. Otherwise extend the current end to max(current_end, end). Never replace it with a smaller nested end.
Trace Interval Merges
Reference
def merge_trace(intervals):
merged=[]
trace=[]
for start,end in sorted(intervals):
if not merged or start > merged[-1][1]:
merged.append([start,end])
else:
merged[-1][1]=max(merged[-1][1],end)
trace.append([item.copy() for item in merged])
return tracePractice
Implement merge_trace(intervals). Sort by start and return the merged list after each input interval is consumed.
Public tests
- Make overlap local after sorting
Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor
Choose Touching or Strict Overlap
For closed intervals, start <= current_end merges touching endpoints. Scheduling with half-open intervals may treat start == current_end as non-overlap. State the endpoint convention before choosing the comparison.
Insert and Merge an Interval
Reference
def insert_interval(intervals, new_interval):
result=[]
start,end=new_interval
index=0
while index<len(intervals) and intervals[index][1] < start:
result.append(intervals[index].copy()); index+=1
while index<len(intervals) and intervals[index][0] <= end:
start=min(start,intervals[index][0]); end=max(end,intervals[index][1]); index+=1
result.append([start,end])
result.extend(item.copy() for item in intervals[index:])
return resultPractice
Implement insert_interval(intervals, new_interval). intervals is sorted and disjoint. Return the merged result without mutating inputs.
Public tests
- Merge touching overlaps without mutation
Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor
Choose Merging or a Sweep Line
Use merging when the output is the union of intervals. Use a sweep line with separate start/end events for maximum concurrency or time-varying counts. Sorting dominates at O(n log n); the merge scan is O(n).
Explain It in an Interview
Say: “After sorting by start, the merged output is disjoint and complete, and only its last interval can overlap the next input.” Mention endpoint semantics, input mutation, and whether output intervals must be copied.
Python Version Note
Complexity & Invariants
Interview bounds depend on the stated representation, input model, and real Python operations.
| Operation | Average | Worst | Interview note |
|---|---|---|---|
| Merge Intervals decision loop | O(n log n) | O(n log n) | Sort copied half-open blocks and extend only the last merged block when strict overlap exists. |
Space
O(n) for the focused Coalesce Busy Blocks implementation.
Assumptions
- Sorted order makes the last merged block the only possible overlap. Strict comparison merges exactly shared time and preserves touching but disjoint half-open boundaries.
- The bound includes real Python operations; no repeated slicing, linear list membership, or hidden sorting is treated as free.
Invariants Worth Saying Aloud
- State the precise Merge Intervals invariant before coding and preserve it after every update, traversal step, or recursive return.
- Output intervals are sorted and pairwise disjoint.
- The last output interval represents the entire current overlap group.
- Sort copied intervals before local merging. Preserve this property after every transition.
- Apply half-open boundary semantics precisely. Preserve this property after every transition.
When To Use Or Avoid Merge Intervals
Use It When
- Use Merge Intervals when the prompt exposes the ordering, monotonicity, recurrence, or constraint that makes this decision safe.
- Use it when output intervals are sorted and pairwise disjoint.
Choose Another Tool When
- Avoid Merge Intervals when its decision rule cannot eliminate work or preserve the required state.
- Avoid forcing the label onto a prompt whose simpler direct scan already meets the constraints.
Common Pitfalls
These are the mistakes most likely to survive a happy-path example and fail a boundary case.
Moving state without a proof
Applying the pattern without proving its ordering, monotonicity, or window invariant can silently miss valid candidates.
Prevent it: Write the decision rule beside the loop and verify it against Coalesce Busy Blocks before optimizing.
Avoid
def coalesce_busy_blocks(blocks):
passUse instead
def coalesce_busy_blocks(blocks):
merged = []
for start, end in sorted([list(block) for block in blocks]):
if merged and start < merged[-1][1]:
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
return mergedWhere you will hit this: Coalesce Busy Blocks(opens in a new tab)
Breaking the maintained state
Uses closed-interval equality and wrongly merges touching half-open blocks.
Prevent it: Use the public tests and preserve this state: Output intervals are sorted and pairwise disjoint.
Avoid
def coalesce_busy_blocks(blocks):
out=[]
for s,e in sorted(blocks):
if out and s<=out[-1][1]: out[-1][1]=max(out[-1][1],e)
else: out.append([s,e])
return outUse instead
def coalesce_busy_blocks(blocks):
merged = []
for start, end in sorted([list(block) for block in blocks]):
if merged and start < merged[-1][1]:
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
return mergedWhere you will hit this: Coalesce Busy Blocks(opens in a new tab)
Hiding Python work in the hot path
Python slicing, copying, membership in lists, or repeated sorting inside the loop can invalidate the intended complexity.
Prevent it: Count every slice, copy, sort, membership check, and container update before claiming O(n log n).
Avoid
def coalesce_busy_blocks(blocks):
out=[]
for s,e in sorted(blocks):
if out and s<=out[-1][1]: out[-1][1]=max(out[-1][1],e)
else: out.append([s,e])
return outUse instead
def coalesce_busy_blocks(blocks):
merged = []
for start, end in sorted([list(block) for block in blocks]):
if merged and start < merged[-1][1]:
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
return mergedWhere you will hit this: First and Last Target Position(opens in a new tab)
Reviewed References
Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.
- Python More on Lists(opens in a new tab)
python-docs · checked 2026-07-27
- LeetCode 56 — Merge Intervals(opens in a new tab)
leetcode · checked 2026-07-26