Merge Intervals
Problem Statement
Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals and return an array of non-overlapping intervals that covers exactly the same ranges.
Input
An integer matrix intervals, where each row represents a closed interval [start, end].
Output
An integer matrix containing the merged, non-overlapping intervals in increasing start order.
Constraints
- •
1 <= intervals.length <= 10^4 - •
intervals[i].length == 2 - •
0 <= starti <= endi <= 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]]Learning Objectives
- Recognise the canonical sort-by-start merge pattern for interval ranges.
- Explain why a single carried interval is enough after sorting by start time.
- Apply the overlap rule **nextStart <= carriedEnd** without off-by-one errors.
- Convert the carried interval into an output list only when a gap appears.
Intuition
Pattern Recognition
The trigger words are merge, overlapping intervals, and return non-overlapping ranges. The trap is trying to compare every pair, or comparing each interval only with its original neighbour after previous merges have already extended the range.
Sort by start so intervals arrive from left to right on the number line. Once sorted, the only active state is the interval you are currently carrying. If the next interval starts before or exactly at the carried end, it overlaps and can only extend the carried end. If it starts after the carried end, no future interval can go back and touch the carried interval, so the carried interval is final.
Common mistakes
- ×Forgetting to sort first, which makes a one-pass merge invalid.
- ×Using **nextStart < carriedEnd** and missing intervals that touch at the same endpoint.
- ×Appending the carried interval too early before all overlapping intervals have extended it.
- ×Comparing the next interval with the last original interval instead of the current merged interval.
Algorithm Explanation
Key idea
Sort intervals by start. Carry one merged interval with a current start and end. For each next interval, if nextStart <= currentEnd, the intervals overlap, so extend currentEnd to max(currentEnd, nextEnd). Otherwise a gap exists, so emit the carried interval and start carrying the next one.
Interval walkthrough
Use intervals = [[1,3],[2,6],[8,10],[15,18]]. On the number line 1--2--3--4--5--6--7--8--9--10--15--18, carry [1,3] first. The next interval [2,6] begins at 2, which is inside the carried interval ending at 3, so the carried range stretches to [1,6]. Then [8,10] starts after 6, creating a gap, so [1,6] is final. Carry [8,10]. The interval [15,18] starts after 10, so [8,10] is final and the last carried interval becomes [15,18].
Algorithm
- Sort intervals by increasing start value.
- Initialise the carried interval from the first sorted interval.
- For each remaining interval, compare its start with the carried end.
- If it overlaps, extend the carried end to the larger end value.
- If it does not overlap, append the carried interval to the result and carry the new interval.
- After the loop, append the final carried interval.
- Convert the result list to an int[][] and return it.
Solutions
Solution: Sort by start and carry one merged interval
Use this as the canonical interview solution whenever intervals can be sorted and the task is to coalesce all overlaps.
Sort intervals by start time, then sweep left to right while carrying one merged interval. Sorting guarantees that if the next interval starts after the carried end, the carried interval can never overlap any later interval.
Step-by-step
- Return an empty matrix if the input is empty.
- Sort intervals by their start value.
- Seed currentStart and currentEnd from the first interval.
- For every next interval, merge it into the carried interval when nextStart <= currentEnd.
- When a gap appears, add the carried interval to the result and reset the carried values.
- Add the final carried interval after the scan and return the result matrix.
O(n log n)
O(n)
Sorting dominates the runtime. The result can hold every interval when nothing overlaps.
Java implementation
Dry Run
Sample input
intervals = [[1,3],[2,6],[8,10],[15,18]]. The intervals are already sorted by start, so the sweep can begin immediately.
| next interval | carried before | overlap test | action | result so far |
|---|---|---|---|---|
| [1,3] | none | first interval | carry [1,3] | [] |
| [2,6] | [1,3] | 2 <= 3 | extend carry to [1,6] | [] |
| [8,10] | [1,6] | 8 > 6 | emit [1,6], carry [8,10] | [[1,6]] |
| [15,18] | [8,10] | 15 > 10 | emit [8,10], carry [15,18] | [[1,6],[8,10]] |
| end | [15,18] | no more intervals | emit final carry | [[1,6],[8,10],[15,18]] |
The carried interval is the only mutable range. It grows from [1,3] to [1,6], then gaps cause final intervals to be emitted.
Interview Tips
State the overlap rule clearly: after sorting by start, nextStart <= currentEnd means merge, otherwise emit. Mention that touching endpoints overlap for this problem. Interviewers often test [[1,4],[4,5]] to catch the strict-inequality mistake.
Likely follow-ups
- How would the solution change if intervals were half-open, meaning **[start, end)**?
- How would you merge intervals as they arrive in a stream without sorting the full history each time?
- How would you return the total covered length instead of the merged intervals?
- How would you handle intervals with extra payload data that must be preserved during merging?
Similar Problems
Key Takeaways
- Sorting by start turns pairwise merging into a one-pass sweep.
- The carried interval represents all overlaps seen so far in the current connected group.
- A gap proves the carried interval is final because all future starts are even larger.
- Closed intervals that touch at an endpoint should be merged in this problem.