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:

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store