Merge Intervals
Problem Statement
Given an array of intervals where intervals[i] = [start, end], merge all overlapping intervals and return an array of the non-overlapping intervals that cover every point from the input.
Input
An integer matrix intervals, where each row is a closed interval [start, end].
Output
A matrix of merged, non-overlapping intervals that covers the same set of points as the input.
Constraints
- •
1 <= intervals.length <= 10^4 - •
intervals[i].length == 2 - •
0 <= start <= end <= 10^4
Examples
Example 1
intervals = [[1,3],[2,6],[8,10],[15,18]]
[[1,6],[8,10],[15,18]]Example 2
intervals = [[1,4],[4,5]]
[[1,5]]Example 3
intervals = [[1,4],[0,2],[3,5]]
[[0,5]]Learning Objectives
- Recognise when sorting intervals by start turns a global overlap problem into a one-pass sweep.
- Maintain the current merged interval and extend only its right endpoint when overlap is detected.
- Explain why earlier intervals never need to be revisited after the sweep passes them.
- Handle endpoint-touching intervals correctly for closed ranges.
Intuition
The greedy insight is to make overlap local. Unsorted intervals can overlap with anything, so every decision feels global. Once intervals are sorted by start, any interval that can overlap the current merged block must appear immediately while its start is still at or before the current end.
The tempting wrong idea is to repeatedly search for overlapping pairs and merge them. That works logically, but it hides the structure and can become slow and messy. Sorting reveals the real pattern: sweep left to right, keep the best current coverage, and only start a new block when the next interval begins after the current end.
Common mistakes
- ×Forgetting to sort first, which makes a single pass invalid.
- ×Treating **start == currentEnd** as non-overlap even though closed intervals overlap at the shared endpoint.
- ×Appending every interval before deciding whether it should extend the previous one.
- ×Updating both start and end on overlap; after sorting by start, the current merged start is already the earliest one.
Algorithm Explanation
Greedy strategy
Sort intervals by starting point. Keep the last merged interval as the current block of coverage. If the next interval starts within that block, extend the block end to the farthest end seen. If it starts after the block, the current block is final and a new block begins.
Why it works
After sorting, all future intervals start no earlier than the current interval. Once an interval starts after the current merged end, no later interval can connect back to the current block because later starts are even larger. Therefore it is safe to close the current block immediately.
Proof of correctness
Consider any optimal merged output after intervals are sorted. The first output interval must begin at the smallest start among the input intervals in its connected component. While subsequent intervals start at or before the current merged end, they belong to the same component and any valid output must cover their farthest end. If an optimal output split this component earlier, exchanging those split pieces for one interval from the earliest start to the farthest end preserves exactly the same coverage and uses no extra intervals. When the next start is greater than the current end, no interval later in sorted order can bridge the gap, so every valid output must start a new interval. Repeating this exchange argument for each component gives exactly the greedy output.
Algorithm
- Sort intervals by start, using end as a tie-breaker.
- Create an empty result list.
- For each interval, compare its start with the end of the last merged interval.
- If there is no last interval or the start is greater than the last end, append a new interval.
- Otherwise, update the last end to max(lastEnd, currentEnd).
- Return the result list as an array.
Solutions
Solution: Sort by start and sweep
Sorting by start makes each overlap decision depend only on the last interval already merged. The result list stores finalized merged blocks, and the final block may keep expanding as long as incoming intervals overlap it.
Step-by-step
- Sort intervals by increasing start so potential overlaps are adjacent.
- Iterate through the sorted intervals.
- If the result is empty or the current interval starts after the last merged end, append a fresh interval.
- Otherwise, merge by extending the last merged end to the maximum of both ends.
- Convert the list of merged intervals back to a matrix.
O(n log n)
O(n)
Sorting dominates the runtime. The output list can contain up to n intervals.
Java implementation
Dry Run
Sample input
intervals = [[1,3],[2,6],[8,10],[15,18]]. Sort by start, then track the current merged interval and output count.
| step | interval after start-sort | current merged before | decision | current merged after | output count |
|---|---|---|---|---|---|
| 1 | [1,3] | none | Start the first merged interval. | [1,3] | 1 |
| 2 | [2,6] | [1,3] | 2 <= 3, so extend the current end to 6. | [1,6] | 1 |
| 3 | [8,10] | [1,6] | 8 > 6, so close the old block and start a new one. | [8,10] | 2 |
| 4 | [15,18] | [8,10] | 15 > 10, so start another block. | [15,18] | 3 |
The sweep produces three disjoint merged blocks: [1,6], [8,10], and [15,18].
Interview Tips
Lead with the sort-then-sweep pattern. Say that sorting by start makes all intervals that can merge with the current block appear before the first interval that starts after the current end. Interviewers often check whether you treat touching endpoints correctly, so explicitly mention that [1,4] and [4,5] merge for closed intervals.
Likely follow-ups
- How would you merge intervals if they arrive as a stream instead of all at once?
- How would you return the total covered length after merging?
- How would the answer change if intervals were open rather than closed?
- How would you merge intervals across multiple already-sorted lists?
Similar Problems
Key Takeaways
- Sorting by start makes overlapping intervals adjacent.
- The current merged interval only needs its end extended on overlap.
- A gap after the current end proves the current merged block is final.
- Endpoint equality counts as overlap for closed intervals.