Merge Intervals
Problem Description
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 all the intervals in the input.
Example 1:
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].
Example 2:
Input: intervals = [[1,4], [4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
Constraints:
1 <= intervals.length <= 10⁴
intervals[i].length == 2
0 <= startᵢ <= endᵢ <= 10⁴
Brute Force Approach
To merge overlapping intervals, we need to determine whether two intervals overlap.
To merge intervals, we first need to figure out if two intervals overlap. Two intervals overlap if one interval starts before the other interval ends, and vice versa.
Formally, if we have two intervals:
- Interval 1: [start1, end1]
- Interval 2: [start2, end2]
They overlap if:
- The start of the second interval (start2) is less than or equal to the end of the first interval (end1), and
- The end of the second interval (end2) is greater than or equal to the start of the first interval (start1).
In simpler terms, this condition checks if one interval starts before the other finishes, meaning they share some common part, or one is contained within the other.
We can now compare them one by one to determine if they overlap.
If two intervals overlap, we merge them by adjusting the ending point of the smaller (earlier) interval.
For example, if Interval 1 is [start1, end1] and Interval 2 is [start2, end2], and they overlap (start2 <= end1 or end2 >= start1), we merge them into a single interval: [min(start1, start2), max(end1, end2)].
This works because the start of the merged interval remains smaller (the smaller start), but the end becomes the maximum of the two intervals' end points (max(end1, end2)), ensuring that we cover both intervals fully.
For example:
Consider intervals [1,4] and [2,6]. To determine if they overlap, we compare the start and end points:
- Since 2 <= 4, the intervals overlap because the start of the second interval falls within the first interval.
- To fully cover both intervals, we know that the merged interval must start at 1 (the smaller of the two starting points, i.e., min(1, 2)) and end at 6 (the maximum of the two end points, i.e., max(4, 6)).
Thus, merging [1,4] and [2,6] results in the interval [1,6].
When two intervals overlap, their combined range is covered from the interval that remains smallest and extends to the interval that is farthest. This is why we take a minimum of two starting points and a maximum of two ending points.
By setting the starting point of the merged interval to the smaller of the two start points and the ending point to the larger of the two end points, we ensure that the merged interval fully encompasses the entire range covered by the two original intervals.
This avoids missing any part of either interval and ensures we are covering the entire overlapping region in one interval.
Approach to Solve the Problem
- Iterate through each interval: Start with the first interval and check for overlaps with all other intervals.
- Check for overlap: For each interval at position iii, compare it with every other interval. If an overlap is found (i.e., the start of the current interval is less than or equal to the end of another, and the end of the other is greater than or equal to the start of the current interval), merge them.
- Merge intervals: When merging, update the starting point to the smaller of the two starts and the ending point to the larger of the two ends. Mark the overlapping interval as visited to ensure it is not reprocessed.
- Continue checking overlaps: After merging, continue checking for further overlaps with the updated interval until no more overlaps are found.
- Add the merged interval: Once no further overlaps are detected for the current interval, add the final merged interval to the result list.
- Repeat for unvisited intervals: Skip any intervals that have already been processed (marked as visited) and proceed to the next unvisited interval.
Let's understand this with an example!
Input: intervals=[[2,6],[1,3],[15,18],[8,10]]
Step-by-step Dry Run:
- Initialization:
- n=4, visited=[false, false, false, false]
merged=[]
- n=4, visited=[false, false, false, false]
- Processing interval [2, 6] (i = 0):
- start=2,end=6, visited[0]=true.
- Check overlap with other intervals:
- [1, 3] overlaps (start=min(2,1)=1, end=max(6,3)=6), visited[1]=true.
- [15, 18] does not overlap.
- [8, 10] does not overlap.
- No further overlaps. Add [1,6] to merged.
merged=[[1,6]]
- Processing interval [1, 3] (i = 1):
- Already visited; skip.
- Processing interval [15, 18] (i = 2):
- start=15,end=18, visited[2]=true.
- Check overlap with other intervals:
- [8, 10] does not overlap.
- No further overlaps. Add [15,18] to merged.
merged=[[1,6], [15,18]]
- Processing interval [8, 10] (i = 3):
- start=8,end=10, visited[3]=true.
- No overlaps. Add [8,10] to merged.
Final Result: merged=[[1,6],[15,18],[8,10]]
How to convert this in code?
- Iterate through the intervals:
- Start with each interval at position i.
- Mark the current interval as visited to prevent processing it again.
- Check overlaps with all other intervals:
- For each interval i, compare it with every other unvisited interval j.
- If they overlap (i.e., intervals[j][0] ≤ end and intervals[j][1] ≥ start), merge them:
- Update start=min(start,intervals[j][0]).
- Update end=max(end,intervals[j][1]).
- Mark the interval j as visited.
- Repeat until no further overlaps:
- Continue checking for overlaps with the updated interval until no more overlapping intervals are found.
- Add the merged interval:
- Once all overlaps for the current interval are processed, add the final merged interval to the result list.
- Process all intervals:
- Skip intervals already marked as visited and continue to the next unvisited interval.
- Return the result:
- After processing all intervals, return the list of merged intervals.
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
int n = intervals.size();
vector<bool> visited(n, false); // Track visited intervals
vector<vector<int>> merged;
// Iterate through each interval
for (int i = 0; i < n; i++) {
// Skip already merged intervals
if (visited[i]) continue;
int start = intervals[i][0];
int end = intervals[i][1];
// Mark the interval as visited
visited[i] = true;
// Check all other intervals for overlap
bool foundOverlap = true;
while (foundOverlap) {
foundOverlap = false;
for (int j = 0; j < n; j++) {
if (!visited[j] && intervals[j][0] <= end && intervals[j][1] >= start) {
// Merge intervals
start = min(start, intervals[j][0]);
end = max(end, intervals[j][1]);
// Mark this interval as visited
visited[j] = true;
// Keep checking for further overlaps
foundOverlap = true;
}
}
}
// Add the merged interval to the result
merged.push_back({start, end});
}
return merged;
}
};2. Java Try on Compiler
class Solution {
public int[][] merge(int[][] intervals) {
int n = intervals.length;
// Track visited intervals
boolean[] visited = new boolean[n];
List<int[]> merged = new ArrayList<>();
// Iterate through each interval
for (int i = 0; i < n; i++) {
// Skip already merged intervals
if (visited[i]) continue;
int start = intervals[i][0];
int end = intervals[i][1];
// Mark the interval as visited
visited[i] = true;
// Check all other intervals for overlap
boolean foundOverlap = true;
while (foundOverlap) {
foundOverlap = false;
for (int j = 0; j < n; j++) {
if (!visited[j] && intervals[j][0] <= end && intervals[j][1] >= start) {
// Merge intervals
start = Math.min(start, intervals[j][0]);
end = Math.max(end, intervals[j][1]);
// Mark this interval as visited
visited[j] = true;
// Keep checking for further overlaps
foundOverlap = true;
}
}
}
// Add the merged interval to the result
merged.add(new int[]{start, end});
}
// Convert the list to a 2D array and return
return merged.toArray(new int[merged.size()][]);
}
}3. Python Try on Compiler
class Solution:
def merge(self, intervals):
n = len(intervals)
# Track visited intervals
visited = [False] * n
merged = []
# Iterate through each interval
for i in range(n):
# Skip already merged intervals
if visited[i]:
continue
start = intervals[i][0]
end = intervals[i][1]
# Mark the interval as visited
visited[i] = True
# Check all other intervals for overlap
found_overlap = True
while found_overlap:
found_overlap = False
for j in range(n):
if not visited[j] and intervals[j][0] <= end and intervals[j][1] >= start:
# Merge intervals
start = min(start, intervals[j][0])
end = max(end, intervals[j][1])
# Mark this interval as visited
visited[j] = True
# Keep checking for further overlaps
found_overlap = True
# Add the merged interval to the result
merged.append([start, end])
return merged4. Javascript Try on Compiler
var merge = function(intervals) {
const n = intervals.length;
const visited = new Array(n).fill(false); // Track visited intervals
const merged = [];
// Iterate through each interval
for (let i = 0; i < n; i++) {
// Skip already merged intervals
if (visited[i]) continue;
let start = intervals[i][0];
let end = intervals[i][1];
// Mark the interval as visited
visited[i] = true;
// Check all other intervals for overlap
let foundOverlap = true;
while (foundOverlap) {
foundOverlap = false;
for (let j = 0; j < n; j++) {
if (!visited[j] && intervals[j][0] <= end && intervals[j][1] >= start) {
// Merge intervals
start = Math.min(start, intervals[j][0]);
end = Math.max(end, intervals[j][1]);
// Mark this interval as visited
visited[j] = true;
// Keep checking for further overlaps
foundOverlap = true;
}
}
}
// Add the merged interval to the result
merged.push([start, end]);
}
return merged;
};Time Complexity: O(n²)
- The time complexity of the given code depends on how the intervals are arranged and whether they overlap. Here's a detailed breakdown:
Worst Case (Non-Overlapping Intervals)
- The outer loop iterates over all n intervals.
- For each interval, the inner loop checks for overlaps with all other intervals, which can take up to n iterations in the worst case.
- This happens when no intervals overlap, as each interval will be processed independently.
- The total number of comparisons in this scenario is n×n=n².
To better understand the time complexity, let's consider the behavior of these comparisons. The number of comparisons made across all intervals can be represented as: 0+1+2+3+⋯+(n−1)
This is the sum of the first n−1 terms, which simplifies to: n(n−1)/2
Therefore, the time complexity of the comparisons is: O(n(n−1)/2)≈O(n²).
Best Case (Fully Overlapping Intervals)
- If all intervals overlap, they will merge into a single interval.
- In this case, an interval will be visited only once in the outer loop, and the inner loop will quickly mark all overlapping intervals as visited in a single pass.
- As a result, the time complexity reduces to O(n) because the total number of operations depends linearly on the number of intervals.
Overall Complexity
- In the worst case (non-overlapping intervals), the time complexity is O(n²).
- In the best case (fully overlapping intervals), the time complexity is O(n).
Thus, the overall complexity of the code is quadratic, O(n²), in the general case where overlaps occur variably.
Space Complexity: O(n)
Auxiliary Space: O(n)
Explanation: The main contributor to space complexity is the result list merged where we store the merged intervals. In the worst case, when all intervals are non-overlapping, this list will contain up to N intervals, hence requiring O(N) space.
Total Space Complexity: O(n)
Explanation: The total space complexity is the space used by merged array and the input array intervals, which is O(N) + O(N) = O(2N) ≈ O(N).
Will Brute Force Work Against the Given Constraints?
The algorithm processes each interval in the input array by iterating through it. The outer loop runs once for each interval, so it iterates n times, where n is the length of the intervals array.
As we saw above the worst-case time complexity of the solution is O(n²).
Most competitive programming platforms, like LeetCode, allow up to 10⁶ operations per test case, meaning your solution should be able to handle this number of operations within the time limits. When multiple test cases are involved, the total number of operations can go up to 10⁸.
For n ≤ 10⁴, the O(n²) time complexity can still be handled within the time limits of most competitive programming environments. The total number of operations would be approximately 10⁸ for n=10⁴, which is within the typical limits of 1-2 seconds for execution. However, if n were larger or if multiple test cases were involved, performance could become a concern.
Additionally, due to less strict test case constraints (such as limited input sizes or fewer test cases), this O(n²) solution may still pass in many competitive programming scenarios, even though it is not the most optimal solution for very large inputs or multiple test cases.
Can we optimize it?
In the previous approach, we used two loops: the first loop was used to select an interval, and the second loop was used to compare it with all subsequent intervals to check for overlaps.
But do we really need two loops to accomplish this?
Not necessarily! We can optimize this process by reducing it to a single loop.
Here’s how we can do it:
In our previous approach, we were iterating through the entire array for each interval, checking for overlaps with all other intervals, because we weren’t sure where the overlapping intervals could be placed within the array. This resulted in unnecessary comparisons and made the process less efficient.
Can we optimize this step?
Yes, we can sort the intervals.
Once the intervals are sorted by their starting point, all the neighboring intervals that could overlap will be positioned next to each other. This allows us to efficiently merge any overlapping intervals by simply comparing each interval with the next one in the sorted array.
First, we sort the intervals by their starting point. Sorting is crucial because it arranges the intervals in a way that makes it easy to check for overlaps sequentially. After sorting, we initialize an empty list called merged to store the intervals after merging them.
Now, as we traverse the intervals, we no longer need a second loop to compare each interval with all others. Instead, we check if the current interval overlaps with the last interval in the merged list. Specifically, for each new interval, we look at the most recent merged interval (i.e., the last interval in the merged list).
If the current interval overlaps with the last merged interval (meaning the starting point of the current interval is less than or equal to the end of the last merged interval), we update the end of the last merged interval to be the maximum of its current end and the end of the current interval. This ensures that we extend the merged interval to cover both intervals.
If there’s no overlap, we simply add the current interval as the new last merged interval.
By doing this, we achieve the same result, but with just one loop through the sorted intervals. This simplifies the code and improves efficiency because we no longer have to use nested loops to check every pair of intervals. Instead, we handle each interval only once, making the solution more streamlined and easy to understand.
Thus, the overall process involves:
- Sorting the intervals.
- Initializing an empty merged list.
- Traversing the sorted intervals and merging them as needed based on overlaps.
Which data structure can be useful here?
Since we are comparing each interval with the last interval in our merged list, can you relate this to a similar property of a data structure?
Yes, there is a data structure that allows us to easily access and compare the last element—the stack.
We can use a stack to store the merged intervals. The key advantage here is that a stack provides easy access to the last inserted element, which aligns perfectly with our need to compare the current interval with the last merged one.
If the intervals overlap, we can simply pop the last interval from the stack, merge it with the current one, and then push the updated interval back onto the stack. If they don’t overlap, we just push the new interval onto the stack as is.
This way, we effectively use the stack's "last-in, first-out" (LIFO) property to manage the merging process, providing a clean and intuitive approach for solving the problem.
But, since using a stack will cost us extra space for building and maintaining the stack, we can actually achieve the same result using a simple vector (or list). The vector already allows us to access the last element efficiently, and we can update or remove it when necessary.
By utilizing the vector, we can avoid the overhead of using an additional data structure like a stack.This gives us a clean, space-efficient solution without the need for extra structures.
This approach significantly reduces the complexity and avoids unnecessary comparisons, ensuring that the solution remains efficient and easy to implement.
Let's understand with visuals
Let's understand this with an example!
merged = []
Iterate through the intervals
- Iteration 1:
Current interval: [1, 3]
Since merged is empty, add [1, 3] to merged.
merged = [[1, 3]] - Iteration 2:
Current interval: [2, 6]
Check if it overlaps with the last interval in merged ([1, 3]). - Yes, overlap exists because 2 ≤ 3.
Merge intervals by updating the end to max(3, 6) = 6.
merged = [[1, 6]]
- Yes, overlap exists because 2 ≤ 3.
- Iteration 3:
Current interval: [8, 10]
No, overlaps with the last merged interval [1, 6] because 8 > 6.
Add [8, 10] to merged.
merged = [[1, 6], [8, 10]] - Iteration 4:
Current interval: [15, 18]
No, overlaps with the last merged interval [8, 10] because 15 > 10.
Add [15, 18] to merged.
merged = [[1, 6], [8, 10], [15, 18]]
Final Output:
Merged intervals: [[1, 6], [8, 10], [15, 18]]
How to convert in code
Sort the intervals based on their starting point.
Create an empty list that will store the merged intervals.
Use a loop to go through each interval:
- If the list is empty or the current interval does not overlap with the last interval in merged, add the current interval.
- If it overlaps, merge the intervals by updating the last interval’s end point to the maximum of the two.
Once all intervals are processed, return the merged list.
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
// size of the intervals
int n = intervals.size();
// sort the intervals based on the starting time
// this ensures that overlapping intervals are next to each other
sort(intervals.begin(), intervals.end());
// a vector to store the merged intervals
vector<vector<int>> merged;
// iterate through each interval
for (int i = 0; i < n; i++) {
// if the merged list is empty, or if the current interval
// does not overlap with the last merged interval, add it to the merged list
if (merged.empty() || intervals[i][0] > merged.back()[1]) {
merged.push_back(intervals[i]);
}
// if the current interval overlaps with the last interval in merged,
// merge them by updating the end of the last merged interval to the max end
else {
merged.back()[1] = max(merged.back()[1], intervals[i][1]);
}
}
// return the merged list of intervals
return merged;
}
};
2. Java Try on Compiler
class Solution {
public int[][] merge(int[][] intervals) {
// size of the intervals
int n = intervals.length;
// sort the intervals based on the starting time
// this ensures that overlapping intervals are next to each other
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
// a list to store the merged intervals
List<List<Integer>> merged = new ArrayList<>();
// iterate through each interval
for (int i = 0; i < n; i++) {
// if the merged list is empty, or if the current interval
// does not overlap with the last merged interval, add it to the merged list
if (merged.isEmpty() || intervals[i][0] > merged.get(merged.size() - 1).get(1)) {
merged.add(Arrays.asList(intervals[i][0], intervals[i][1]));
}
// if the current interval overlaps with the last interval in merged,
// merge them by updating the end of the last merged interval to the max end
else {
merged.get(merged.size() - 1).set(1, Math.max(merged.get(merged.size() - 1).get(1), intervals[i][1]));
}
}
// convert the merged list back to an int[][] array
int[][] result = new int[merged.size()][2];
for (int i = 0; i < merged.size(); i++) {
result[i][0] = merged.get(i).get(0);
result[i][1] = merged.get(i).get(1);
}
// return the merged array
return result;
}
}
3. Python Try on Compiler
class Solution:
def merge(self, intervals):
# size of the intervals
n = len(intervals)
# sort the intervals based on the starting time
intervals.sort(key=lambda x: x[0])
# a list to store the merged intervals
merged = []
# iterate through each interval
for i in range(n):
# if the merged list is empty, or if the current interval
# does not overlap with the last merged interval, add it to the merged list
if not merged or intervals[i][0] > merged[-1][1]:
merged.append(intervals[i])
# if the current interval overlaps with the last interval in merged,
# merge them by updating the end of the last merged interval to the max end
else:
merged[-1][1] = max(merged[-1][1], intervals[i][1])
# return the merged list of intervals
return merged
4. Javascript Try on Compiler
var merge = function(intervals) {
// size of the intervals
const n = intervals.length;
// sort the intervals based on the starting time
// this ensures that overlapping intervals are next to each other
intervals.sort((a, b) => a[0] - b[0]);
// an array to store the merged intervals
const merged = [];
// iterate through each interval
for (let i = 0; i < n; i++) {
// if the merged list is empty, or if the current interval
// does not overlap with the last merged interval, add it to the merged list
if (merged.length === 0 || intervals[i][0] > merged[merged.length - 1][1]) {
merged.push(intervals[i]);
}
// if the current interval overlaps with the last interval in merged,
// merge them by updating the end of the last merged interval to the max end
else {
merged[merged.length - 1][1] = Math.max(merged[merged.length - 1][1], intervals[i][1]);
}
}
// return the merged list of intervals
return merged;
};Time Complexity: O(n log n)
First, we sort the intervals based on their starting points. Sorting a list of N intervals takes O(N log N).
After sorting, we traverse the list of intervals in a single loop. For each interval, we either:
1. Add it directly to the merged list if there’s no overlap, or
2. Merge it with the last interval in the merged list if there is an overlap.
This traversal is done in O(N), as each interval is processed once.
The total time complexity is determined by both the sorting step and the linear traversal step. Since O(NlogN) dominates O(N) the overall time complexity is: O(NlogN)
Space Complexity: O(n)
Auxiliary Space:
The main contributor to space complexity is the result list merged where we store the merged intervals. In the worst case, when all intervals are non-overlapping, this list will contain up to N intervals, hence requiring O(N) space.
Total Space Complexity:
The total space complexity is the space used by merged array and the input array intervals, which is O(N) + O(N) = O(2N) ≈ O(N)
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
You are given an array of non-overlapping intervals [intervals] where intervals[i] = [starti, endi] represent the start and the end of the ith interval and [intervals] is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.
Insert newInterval into [intervals] such that [intervals] is still sorted in ascending order by starti and [intervals] still does not have any overlapping intervals (merge overlapping intervals if necessary).
Return [intervals] after the insertion.
Note that you don't need to modify [intervals] in-place. You can make a new array and return it.
We are given an array [asteroids] of integers representing asteroids in a row.
For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.
Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.