Merge Intervals
MediumGiven an array of intervals
where intervals[i] = [starti, endi],
merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
Example
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].
Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
Explanation
The key insight to solve this problem efficiently is to sort the intervals by their start time. Once sorted, we can iterate through the intervals and merge them one by one if they overlap with the previous merged interval.
Two intervals [a, b]
and [c, d]
overlap if and only if c <= b
(the start of the second interval is less than or equal to the end of the first).
If they overlap, we merge them by creating a new interval with start = min(a, c)
and end = max(b, d).
Since we're sorting by start time, we know a <= c,
so the merged interval is [a, max(b, d)].
We maintain a result list where we add merged intervals. For each interval in the sorted array:
- If the result is empty or the current interval doesn't overlap with the last interval in result, add it to result
- If it overlaps with the last interval in result, merge them by updating the end of the last interval
This greedy approach works because sorting ensures we process intervals in order, and any interval that could overlap with a previous one will be adjacent to it in the sorted order.
Idea Map
Sort intervals by start time
Initialize result = []
For each interval in sorted intervals
If result empty OR interval[0] > result[-1][1]:
Add interval to result
Else:
Set result[-1][1] = max(result[-1][1], interval[1])
Complexity Analysis
Time Complexity
O(n log n) - Sorting the intervals takes O(n log n) time. The subsequent iteration through the sorted intervals is O(n). The overall complexity is dominated by sorting.
Space Complexity
O(n) or O(log n) - Depending on the sorting algorithm. The result list can be up to O(n) in the worst case (no overlaps). In-place sorting uses O(log n) for the recursion stack.
Code
def merge(intervals):
Initializes the function `merge` which takes a list of intervals as input.
if not intervals:
Checks if the input list is empty and returns empty list if true - edge case handling.
return []
Return empty list for empty input.
intervals.sort(key=lambda x: x[0])
Sorts intervals by their start time (first element) using a lambda function as the key.
merged = [intervals[0]]
Initialize result list with the first interval - we'll merge subsequent intervals into this.
for i in range(1, len(intervals)):
Loop through remaining intervals starting from index 1 (second interval).
if intervals[i][0] > merged[-1][1]:
Check if current interval's start is greater than last merged interval's end - no overlap condition.
merged.append(intervals[i])
If no overlap, add current interval as a new entry to the merged list.
else:
If there IS an overlap (start <= end of last merged interval).
merged[-1][1] = max(merged[-1][1], intervals[i][1])
Merge by extending the end of the last interval to the maximum of both ends.
return merged
Return the list of merged intervals.
public int[][] merge(int[][] intervals) {
Initializes the function `merge` which takes a 2D array of intervals as input.
if (intervals == null || intervals.length == 0) {
Checks if the input array is null or empty - edge case handling.
return new int[0][];
Return empty 2D array for null or empty input.
}
End of the if statement.
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
Sorts intervals by their start time using a lambda comparator that compares first elements.
List<int[]> merged = new ArrayList<>();
Creates an ArrayList to store merged intervals dynamically.
merged.add(intervals[0]);
Add the first (now smallest) interval to the result list.
for (int i = 1; i < intervals.length; i++) {
Loop through remaining intervals starting from index 1.
int[] last = merged.get(merged.size() - 1);
Get the last interval in our merged list for comparison.
if (intervals[i][0] > last[1]) {
Check if current interval's start is greater than last merged interval's end - no overlap.
merged.add(intervals[i]);
If no overlap, add current interval as a new entry to the merged list.
} else {
If there IS an overlap (start <= end of last merged interval).
last[1] = Math.max(last[1], intervals[i][1]);
Merge by extending the end of the last interval to the maximum of both ends.
}
End of the if-else statement.
}
End of the for loop.
return merged.toArray(new int[merged.size()][]);
Convert ArrayList to 2D array and return it.
}
End of the function.
vector<vector<int>> merge(vector<vector<int>>& intervals) {
Initializes the function `merge` which takes a reference to a 2D vector of intervals as input.
if (intervals.empty()) return {};
Check if input is empty and return empty vector if true - edge case handling.
sort(intervals.begin(), intervals.end());
Sort intervals by start time - vector sorting compares first element by default.
vector<vector<int>> merged;
Create result vector to store merged intervals.
merged.push_back(intervals[0]);
Add the first (now smallest) interval to the result vector.
for (int i = 1; i < intervals.size(); i++) {
Loop through remaining intervals starting from index 1.
if (intervals[i][0] > merged.back()[1]) {
Check if current interval's start is greater than last merged interval's end - no overlap.
merged.push_back(intervals[i]);
If no overlap, add current interval as a new entry to the merged vector.
} else {
If there IS an overlap (start <= end of last merged interval).
merged.back()[1] = max(merged.back()[1], intervals[i][1]);
Merge by extending the end of the last interval to the maximum of both ends.
}
End of the if-else statement.
}
End of the for loop.
return merged;
Return the vector of merged intervals.
}
End of the function.
Edge Cases & Common Mistakes
Forgetting to sort first
The algorithm depends on intervals being sorted by start time. Without sorting, intervals that should be merged might not be adjacent, leading to incorrect results.
Edge case: Single interval or empty input
Always check if the input is empty or contains only one interval. Return the input as-is in these cases - no merging needed.
Touching intervals are considered overlapping
Intervals [1,4] and [4,5] overlap because they touch at point 4. Use `>=` not `>` when checking for overlap to handle this correctly.
Related Problems
Learn More About Interval Problems
Interval problems are a common class of algorithmic challenges that involve overlapping ranges, scheduling, and merging. Understanding the core patterns helps you tackle variations like meeting rooms, employee free time, and more.
Learn more about interval problems →Disclaimer: This problem is for educational purposes. Practice the 'Merge Intervals' problem on LeetCode.