If you want to master array problems, “Merge Intervals” is a must-know question! In this blog, we’ll explain the problem, walk you through both brute force and optimal solutions, and make everything easy to understand with comments, dry runs, and clear explanations.
Given 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.
Here’s the [Problem Link] to begin with.
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 <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104
Brute Force Solution
Intuition and Approach
Let’s solve the problem step by step in the simplest way:
- Sort the Intervals:
Sorting helps us line up all intervals so that overlapping intervals are next to each other. - Check Each Interval:
For every interval, try to merge it with all future intervals that overlap with it. - Skip Already Merged Intervals:
If an interval is already covered by a previous merge, skip it. - Why does this work?
We check every possible overlap and merge accordingly. This ensures all intervals are merged correctly, but it’s not the most efficient.
Code Implementation
from typing import List
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
n = len(intervals)
intervals.sort() # sort intervals by start time
ans = []
for i in range(n):
start, end = intervals[i][0], intervals[i][1] # current interval
# skip if current interval is already merged
if len(ans) != 0 and end <= ans[-1][1]:
continue
# try to merge with future overlapping intervals
for j in range(i + 1, n):
if intervals[j][0] <= end: # overlap found
end = max(end, intervals[j][1]) # extend end to the farthest overlap
else:
break # stop if no overlap
ans.append([start, end]) # add merged interval to answer
return ans
PythonCode Explanation
- First, we sort the intervals to make overlapping intervals adjacent.
- For each interval, we check if it’s already merged; if so, we skip it.
- Then, we look ahead to merge all intervals that overlap with the current one.
- We add the merged interval to our answer list.
Dry Run
Input:intervals = [[1],,,]
- After sorting:
[[1],,,]
- Start with . overlaps, so merge to .
- does not overlap, so add .
- does not overlap, so add .
- Final output:
[[1],,]
Time and Space Complexity
- Time Complexity: O(N^2)
For each interval, we may check all future intervals. - Space Complexity: O(N)
For the answer list.
Conclusion
The brute force approach is easy to understand but slow for large lists. It’s good for learning the basics of the problem.
Optimal Solution
Intuition and Approach
We can solve this problem much faster by merging intervals as we go:
- Sort the Intervals:
Sorting puts overlapping intervals next to each other. - Merge on the Go:
As we go through each interval, check if it overlaps with the last interval in our answer list. If it does, merge them. If not, add it as a new interval. - Why does this work?
After sorting, all overlaps are adjacent, so we only need to look at the last merged interval.
Code Implementation
from typing import List
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
n = len(intervals)
intervals.sort() # sort intervals by start time
ans = []
for i in range(n):
# if ans is empty or no overlap, add interval
if len(ans) == 0 or intervals[i][0] > ans[-1][1]:
ans.append(intervals[i])
else:
# merge with the last interval in ans
ans[-1][1] = max(ans[-1][1], intervals[i][1])
return ans
PythonCode Explanation
- We sort the intervals.
- For each interval, if it doesn’t overlap with the last interval in the answer, we add it.
- If it does overlap, we merge it with the last interval by updating the end value.
Dry Run
Input:intervals = [[1],,,]
- After sorting:
[[1],,,]
- : add to answer →
[[1]]
- : overlaps with , merge to →
[[1]]
- : no overlap, add →
[[1],]
- : no overlap, add →
[[1],,]
Time and Space Complexity
- Time Complexity: O(N log N)
Sorting dominates; merging is O(N). - Space Complexity: O(N)
For the answer list.
Conclusion
The optimal solution is efficient and elegant. It’s the best approach for interviews and large datasets.
Final Thoughts
The “Merge Intervals” problem is a great example of how sorting and merging can simplify complex problems. Start with brute force to understand the basics, then use the optimal solution for best performance.
For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.