Previous posts were about Sliding Window, Two Pointers and Fast & Slow Pointers patterns and today, we will introduce Merge Intervals pattern which is very useful to solve the problems involve intervals, overlapping items that need to be merged etc.
Problem: Merge Intervals
Given a collection of intervals, merge all overlapping intervals.
Input: [[1, 3], [2, 6], [8, 10], [15, 18]] Output: [[1, 6], [8, 10], [15, 18]] Explanation: Since intervals [1, 3] and [2, 6] overlaps, merge them into [1, 6].
Input: [[1, 4], [4, 5]] Output: [[1, 5]] Explanation: Intervals [1, 4] and [4, 5] are considered overlapping.
Merge Intervals Solution
Given two intervals A and B, there will be six different ways the two intervals can relate to each other:
a.start <= b.start, only 1, 2 and 3 are possible from the above scenarios.
Our goal is to merge the intervals whenever they overlap. For the two overlapping scenarios 2 and 3, this is how we will merge them:
We are going to merge them into a new interval
c such that;
c.start = a.start c.end = max(a.end, b.end)
Here is what our code will look like:
class Solution: def merge(self, intervals): if len(intervals) < 2: return intervals intervals.sort(key=lambda x: x) merged =  start = intervals end = intervals for i in range(1, len(intervals)): interval = intervals[i] if interval <= end: # overlapping intervals end = max(interval, end) else: # non-overlapping interval, add the previous interval and reset merged.append([start, end]) start = interval end = interval merged.append([start, end]) # add the last interval return merged
Time Complexity: O(N * log N) where N is the total number of intervals. In the beginning, since we sort the intervals, our algorithm will take O(N * log N) to run.
Space Complexity: O(N), as we need to return a list containing all the merged intervals.
How to identify?
This approach is quite useful when dealing with intervals, overlapping items or merging intervals.
When the problem involves these clue words, you should think about Merge Intervals pattern.