# Coding Patterns: Merge Intervals

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:

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:

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.