Merge Intervals
Asked at Amazon, Apple, Microsoft, Netflix, Oracle, Uber, Atlassian, Databricks, Rippling, Salesforce, Walmart
Problem
Given an array of intervals where each interval is a start and end pair, merge all overlapping intervals and return the non-overlapping result. This problem tests your ability to sort, compare, and handle edge cases cleanly.
Asked At
| Company | Difficulty | |
|---|---|---|
| Amazon | Medium | View all Amazon questions → |
| Apple | Medium | View all Apple questions → |
| Microsoft | Medium | View all Microsoft questions → |
| Netflix | Medium | View all Netflix questions → |
| Oracle | Medium | View all Oracle questions → |
| Uber | Medium | View all Uber questions → |
| Atlassian | Medium | View all Atlassian questions → |
| Databricks | Medium | View all Databricks questions → |
| Rippling | Medium | View all Rippling questions → |
| Salesforce | Medium | View all Salesforce questions → |
| Walmart | Medium | View all Walmart questions → |
How to Think About It
Brute force: compare every pair of intervals to find overlaps. That's O(n²). You'd need to keep merging until no more overlaps exist. Tedious and slow.
Key insight: if you sort intervals by start time, all overlapping intervals become adjacent. You only need one pass through the sorted array to merge them.
Why sorting works: consider [[1,3],[2,6],[8,10]]. After sorting by start: [[1,3],[2,6],[8,10]]. Now [1,3] and [2,6] are adjacent — you can compare them directly. Without sorting, you'd have to check every pair.
The merge rule: after sorting, compare current interval's start with the last merged interval's end. If current start <= last end, they overlap — merge by extending last end to max(last end, current end). If current start > last end, no overlap — append current interval to result.
Visual walkthrough for [[1,3],[2,6],[8,10],[15,18]]:
Sort: [[1,3],[2,6],[8,10],[15,18]]
- Start with result = [[1,3]]
- [2,6]: 2 <= 3 (overlaps). Merge: [1, max(3,6)] = [1,6]. Result = [[1,6]]
- [8,10]: 8 > 6 (no overlap). Append. Result = [[1,6],[8,10]]
- [15,18]: 15 > 10 (no overlap). Append. Result = [[1,6],[8,10],[15,18]]
Note: [1,3] and [2,6] merged into [1,6] because 2 <= 3.
Edge cases: completely contained intervals like [1,10] and [2,5] — the max keeps the outer boundary. Back-to-back intervals like [1,3] and [3,5] — these overlap (3 <= 3). Single interval — return as-is.
Optimal Approach
Step 1: Sort intervals by start time.
Step 2: Initialize result with the first interval.
Step 3: For each subsequent interval:
- Compare current start with last merged end
- If they overlap (current start <= last end): extend last end to max(last end, current end) - If no overlap: append current interval to result
The key insight is that sorting guarantees overlapping intervals are adjacent. You never need to look back — just compare with the last merged interval.
Time: O(n log n) for sorting. Space: O(n) for the result array (O(log n) if you ignore output).
What Trips People Up in Real Interviews
Forgetting to sort first. Without sorting, you can't guarantee that overlapping intervals are adjacent. Sort by start time — this is the prerequisite for the O(n log n) merge pass.
Confusing "merge" with "check overlap." You need to merge intervals that overlap, not just identify them. Two intervals [a, b] and [c, d] overlap if c <= b (assuming sorted by start).
Not handling the case where one interval is entirely contained within another. If [1, 10] contains [2, 5], the merged result is [1, 10], not [1, 5].
Forgetting to add the last interval after the loop. The merge loop only adds intervals when it detects a non-overlap — the final interval is never compared, so add it manually.
Sorting by end time instead of start time. Sorting by end time doesn't guarantee overlapping intervals are adjacent — you need to sort by start time for the linear merge pass to work.
Solution Code
def merge(intervals):
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for start, end in intervals[1:]:
if start <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
return mergedFrequently Asked Questions
What is the Merge Intervals problem?
Given an array of intervals where each interval is a start and end pair, merge all overlapping intervals and return the non-overlapping result. This problem tests your ability to sort, compare, and handle edge cases cleanly.
How do you solve Merge Intervals?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Merge Intervals?
Merge Intervals is asked at Amazon, Apple, Microsoft, Netflix, Oracle, Uber, Atlassian, Databricks, Rippling, Salesforce, Walmart. It is a medium difficulty problem.
What are common mistakes on Merge Intervals?
- Forgetting to sort first. Without sorting, you can't guarantee that overlapping intervals are adjacent. Sort by start time — this is the prerequisite for the `O(n log n)` merge pass.
- Confusing "merge" with "check overlap." You need to merge intervals that overlap, not just identify them. Two intervals [a, b] and [c, d] overlap if c <= b (assuming sorted by start).
- Not handling the case where one interval is entirely contained within another. If `[1, 10]` contains `[2, 5]`, the merged result is `[1, 10]`, not `[1, 5]`.
- Forgetting to add the last interval after the loop. The merge loop only adds intervals when it detects a non-overlap — the final interval is never compared, so add it manually.
- Sorting by end time instead of start time. Sorting by end time doesn't guarantee overlapping intervals are adjacent — you need to sort by start time for the linear merge pass to work.