Merge Intervals
Problem
Given a collection of intervals, merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.
- 1 ≤ intervals.length ≤ 10⁴
- intervals[i].length == 2
- 0 ≤ start_i ≤ end_i ≤ 10⁴
Example
intervals = [[1,3],[2,6],[8,10],[15,18]][[1,6],[8,10],[15,18]]The intervals [1,3] and [2,6] overlap because 2 <= 3. Merging them results in [1,6]. The other intervals do not overlap with this merged interval or each other, so they remain unchanged. The final output is [[1,6],[8,10],[15,18]].
Approach
Straightforward Solution
A brute-force approach would compare every interval with every other interval to check for overlaps, resulting in O(n^2) time complexity, which is inefficient for large inputs.
Core Observation
Overlapping intervals can be merged if they share any common range. Sorting intervals by their start times places all potentially overlapping intervals consecutively, enabling a linear scan to merge them efficiently.
Path to Optimal
Sorting intervals by their start times ensures that any overlapping intervals appear next to each other. This allows a single pass through the sorted list to merge intervals by comparing the current interval's start with the last merged interval's end. If they overlap, merge by updating the end; otherwise, add the current interval as a new merged interval.
Optimal Approach
Sort the intervals by their start times. Initialize the output list with the first interval. Iterate through the remaining intervals, and for each, check if it overlaps with the last interval in the output. If it does, merge by updating the end to the maximum of both ends. If not, append the current interval to the output. This approach runs in O(n log n) due to sorting and O(n) for merging.
Time
O(n log n)
Sorting the intervals dominates the runtime with O(n log n). The subsequent single pass to merge intervals is O(n), which does not increase the overall complexity.
Space
O(n)
The output list stores merged intervals and can be as large as the input in the worst case (no overlaps). The sorting operation may also require O(n) space depending on the sorting algorithm used.
Pattern Spotlight
Merge Intervals (Sorting and Linear Merge)
Sorting intervals by start time aligns all overlapping intervals consecutively, enabling a single linear pass to merge by comparing current interval start with the last merged interval end, thus reducing a complex pairwise overlap problem to a simple linear scan.
Solution
| 1 | class Solution:
|
| 2 | def merge(self, intervals: list[list[int]]) -> list[list[int]]:
|
| 3 | intervals.sort(key = lambda i : i[0])
|
| 4 | output = [intervals[0]]
|
| 5 |
|
| 6 | for start, end in intervals[1:]:
|
| 7 | last_end = output[-1][1]
|
| 8 |
|
| 9 | if start <= last_end:
|
| 10 | output[-1][1] = max(last_end, end)
|
| 11 | else:
|
| 12 | output.append([start, end])
|
| 13 |
|
| 14 | return output |
Step-by-Step Solution
Sort Intervals by Start Time to Align Overlaps
| 3 | intervals.sort(key = lambda i : i[0])
|
Objective
To arrange intervals so that any overlapping intervals appear consecutively, enabling efficient merging.
Key Insight
Sorting by the start time is the foundational step that transforms the problem from a complex pairwise overlap check into a linear scan. This ordering guarantees that when iterating, any interval that overlaps with the previous merged interval will be adjacent, allowing immediate detection and merging.
Interview Quick-Check
Core Logic
Sorting intervals by their start times ensures that all overlapping intervals are grouped together, enabling a linear merge.
Common Pitfalls & Bugs
Failing to sort intervals first can cause missed overlaps or incorrect merges, as intervals may appear out of order.
Initialize Merged List with First Interval
| 4 | output = [intervals[0]]
|
Objective
To start the merged intervals list with the earliest interval as a baseline for subsequent merges.
Key Insight
By initializing the output with the first interval, the algorithm sets a reference interval to compare against. This avoids edge cases in the loop and simplifies the merging logic by always comparing the current interval with the last merged interval.
Interview Quick-Check
Core Logic
Initializing the output with the first interval provides a starting point for merging subsequent intervals.
State & Boundaries
This step assumes the input list is non-empty, as per problem constraints.
Iterate Through Intervals and Merge Overlaps
| 6 | for start, end in intervals[1:]:
|
| 7 | last_end = output[-1][1]
|
| 9 | if start <= last_end:
|
| 10 | output[-1][1] = max(last_end, end)
|
| 11 | else:
|
| 12 | output.append([start, end])
|
Objective
To scan through the sorted intervals and merge any that overlap with the last merged interval.
Key Insight
The key operation is comparing the current interval's start with the last merged interval's end. If they overlap (current start <= last end), the intervals are merged by updating the end to the maximum of both ends. If they do not overlap, the current interval is appended as a new merged interval. This linear scan leverages the sorted order to efficiently merge all overlapping intervals in one pass.
Interview Quick-Check
Core Logic
Merging intervals relies on checking if the current interval's start is less than or equal to the last merged interval's end, then updating the end accordingly.
State & Boundaries
The loop starts from the second interval since the first is already in the output.
Common Pitfalls & Bugs
Incorrectly updating the end or appending intervals can lead to missed merges or duplicated intervals.
Return the List of Merged Intervals
| 14 | return output |
Objective
To output the final merged intervals after processing all input intervals.
Key Insight
After the linear merge pass, the output list contains all non-overlapping intervals covering the original intervals. Returning this list completes the solution.
Interview Quick-Check
Core Logic
Returning the merged intervals list provides the final answer as required by the problem.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
if start <= last_end:Check if the current interval overlaps with the last merged interval.
This condition detects overlap by verifying if the current interval's start is less than or equal to the last merged interval's end, which is the key to deciding whether to merge.
intervals.sort(key = lambda i : i[0])Sort the intervals by their start times in ascending order.
Sorting aligns all intervals so that overlapping intervals are adjacent, enabling a single linear pass to merge them efficiently.
output[-1][1] = max(last_end, end)Merge the current interval by updating the last merged interval's end.
Updating the end to the maximum of both intervals ensures the merged interval covers the entire overlapping range, preserving correctness.
else:Handle the case where intervals do not overlap.
If no overlap exists, the current interval is distinct and must be appended as a new merged interval to the output.
output = [intervals[0]]Initialize the output list with the first interval.
Starting with the first interval provides a baseline for merging subsequent intervals and avoids edge cases in the loop.
last_end = output[-1][1]Retrieve the end of the last merged interval.
Accessing the last merged interval's end is necessary to determine if the current interval overlaps with it.
output.append([start, end])Append the current interval to the output list.
Adding the non-overlapping interval preserves all intervals in the final merged list without losing any coverage.
return outputReturn the list of merged intervals.
Returning the output completes the function, providing the final merged intervals as required.
for start, end in intervals[1:]:Iterate over intervals starting from the second interval.
The loop processes each interval in order, comparing it to the last merged interval to decide whether to merge or append.
Test Your Understanding
Why is sorting intervals by their start time critical before merging?
Sorting ensures that all overlapping intervals are adjacent, so a single linear pass can merge them efficiently without needing to compare every pair, reducing the complexity from O(n^2) to O(n log n).
Related Problems
Intervals pattern
Don't just read it. Drill it.
Reconstruct Merge Intervals from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Merge Intervals drill