Identifying the interval merging pattern
The interval merging technique can only be applied to some specific problems. These are generally easy or medium problems where we are given an array of intervals, and merging all overlapping intervals partially or entirely solves the problem. If the problem statement or its solution follows the generic template below, it can be solved by applying the fixed-sized sliding window technique.
Example
Let's consider the following problem as an example to better understand how to identify and solve a problem using the interval merging technique.
Problem statement: Given an array of start and end times of expected deliveries for a day. Find the minimum number of non-overlapping intervals in the day when at least one delivery is expected at any time in each interval.
Find minimum nonoverlapping times with at least one delivery at any moment.
Interval merging technique
The overlapping intervals in the given array can be merged to find all non-overlapping intervals in the day. At least one delivery is expected at any time in each merged interval, and the number of merged intervals is also the minimum number of intervals satisfying the given condition. The problem description fits the template for the interval merging pattern.
Given an array of intervals (delivery intervals), merge all overlapping intervals.
We can use the interval merging technique to merge all intervals and return non-overlapping intervals for the day.
Use the interval merging technique to merge all overlapping intervals in the times array.
The implementation of the interval merging solution is given as follows.
C++
Java
Typescript
Javascript
Python
As the code above demonstrates, using the interval merging technique, we solve the problem in a single pass in linear O(N) time.
Example problems
Most problems that fall under this category are easy or medium problems; a list of a few is given below.
We will now solve these problems to understand the interval merging pattern better.