Merge Intervals

In this blog post, I will be giving a brief description about another pattern that is very important for technical interviews. The pattern is called merge intervals.

This pattern is used to solve problems that involve intervals, overlapping items that need to be merged etc. In most of the problems that involve intervals, you either need to find overlapping intervals or merge intervals if they overlap.

Problem that include Merge Intervals:

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

Given two intervals [A and B], there can be six different ways the two intervals can relate to each other:

source: emre.me

Identification of Merge Intervals:

We can identify if the problem uses merge intervals pattern by following ways;

• If a question asks us to produce a list with only mutually exclusive intervals
• If a question has a term “overlapping intervals” in it.

References:

Coding Patterns: Merge Intervals

14 Patterns to Ace Any Coding Interview Question