Coding Patterns: Merge Intervals

3 minute read

In Coding Patterns series, we will try to recognize common patterns underlying behind each algorithm question, using real examples from Leetcode.

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

LeetCode 56 - Merge Intervals [medium]

Given a collection of intervals, merge all overlapping intervals.

Example 1:

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].

Example 2:

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:

Merge Intervals

If 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:

Merging Example

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[0])
        
        merged = []
        start = intervals[0][0]
        end = intervals[0][1]
        
        for i in range(1, len(intervals)):
            interval = intervals[i]
            if interval[0] <= end:  # overlapping intervals
                end = max(interval[1], end)
            else:  # non-overlapping interval, add the previous interval and reset
                merged.append([start, end])
                start = interval[0]
                end = interval[1]
            
        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.

Similar LeetCode Problems