How Do You Solve the Merge Intervals Problem?
Learn how to solve the merge intervals problem with a sort-by-start sweep, its complexity, and how to answer this interview question.
Expected Interview Answer
The merge intervals problem asks you to collapse a set of possibly-overlapping intervals into the minimal set of non-overlapping intervals that cover the same ranges, and it is solved by sorting intervals by start time then sweeping through, merging any interval whose start is less than or equal to the current merged interval's end.
After sorting by start time in O(n log n), initialize the result with the first interval, then for each subsequent interval compare its start to the end of the last interval in the result. If it overlaps or touches, extend the last result interval's end to the max of the two ends; otherwise, push the new interval as a fresh entry. This single linear pass after sorting runs in O(n log n) total and O(n) extra space for the result. The pattern generalizes to calendar-conflict detection, IP range compaction, and any 'collapse overlapping ranges' problem.
- O(n log n) via one sort and a single linear sweep
- Produces the minimal covering set of intervals
- Simple in-place-style extension logic, easy to reason about
- Foundation for calendar, range-compaction, and diffing problems
AI Mentor Explanation
A ground's maintenance log lists many overlapping closure windows submitted by different curators for pitch relaying. To publish a clean schedule, the groundskeeper sorts all windows by start date, then walks through merging any window that begins before or exactly when the current closure ends, stretching the closure's end date outward as needed. The moment a window starts strictly after the current closure ends, it becomes a brand-new closure block. The final published list is the smallest number of closure blocks that still cover every requested day.
Step-by-Step Explanation
Step 1
Sort by start time
Sort all intervals ascending by their start value in O(n log n).
Step 2
Seed the result with the first interval
Push the first sorted interval into the result list.
Step 3
Merge or append on each scan step
If the current interval overlaps the last result interval (start <= last.end), extend last.end to max(last.end, current.end); otherwise append it as new.
Step 4
Return the collapsed list
The result list is the minimal set of non-overlapping intervals covering all input ranges.
What Interviewer Expects
- Sort by start time before scanning
- Handle the "touching" edge case (start == previous end) as an overlap correctly
- State O(n log n) time and O(n) space
- Distinguish merging from interval scheduling maximization (a different problem)
Common Mistakes
- Forgetting to sort first, assuming input is already ordered
- Using strict < instead of <= when checking overlap, missing touching intervals
- Mutating the input list while iterating instead of building a new result
- Comparing against the original last interval instead of the possibly-extended merged one
Best Answer (HR Friendly)
“When I need to collapse a messy list of overlapping ranges into the cleanest possible set, I sort them by start time and then walk through once, stretching the current range whenever the next one overlaps it, or starting a new range when it does not. It is a straightforward sort-then-sweep pattern that shows up constantly in calendar and range problems.”
Code Example
def merge_intervals(intervals):
if not intervals:
return []
intervals = sorted(intervals, key=lambda iv: iv[0])
merged = [intervals[0]]
for start, end in intervals[1:]:
last_start, last_end = merged[-1]
if start <= last_end:
merged[-1] = (last_start, max(last_end, end))
else:
merged.append((start, end))
return merged
print(merge_intervals([(1, 3), (2, 6), (8, 10), (15, 18)]))
# [(1, 6), (8, 10), (15, 18)]Follow-up Questions
- How would you insert one new interval into an already-merged list efficiently?
- How would you find the total covered length after merging?
- How would you handle merging when intervals come from a live stream instead of a fixed array?
- How is this different from the interval scheduling maximization problem?
MCQ Practice
1. What must you do before sweeping through intervals to merge them?
Sorting by start time ensures overlapping candidates are always adjacent during the single linear sweep.
2. Two intervals (1, 5) and (5, 8) — should they be merged?
Using <= treats touching intervals as overlapping, correctly merging them into (1, 8).
3. What is the overall time complexity of the merge intervals algorithm?
Sorting dominates at O(n log n); the merge sweep itself is O(n).
Flash Cards
What do you sort by before merging intervals? — Start time, ascending.
When do you merge two intervals in the sweep? — When the current interval’s start is <= the last merged interval’s end.
What is the time complexity of merge intervals? — O(n log n), dominated by the sort.
What space does merge intervals use? — O(n) for the result list (O(log n) extra for the sort itself).