# Maximum Number of Overlapping Intervals

## Introduction

In this blog, we will discuss how to find the Maximum Number of Overlapping Intervals. It is an important problem to get a strong grip over greedy algorithms and is a good sorting application.

A common prerequisite is having a basic knowledge of sorting and how comparators are written. Without knowing this, it is recommended to learn sorting and comparators. Nevertheless, we’ll try to cover each point in-depth that is required to find the Maximum number of overlapping intervals.

What do we mean by the Overlapping Intervals?

Well, it’s a trivial question, but still, for the sake of clarity, we’ll define that let

Two intervals be [a, b], and  [c, d], where a<=b and c <= d, are said to be overlapping iff their intersection is not empty. In the mathematical form, we can write as:

Two intervals [a, b] and [c, d] are said to be overlapping if,

→ a <= c <= b <= d

Or,

→  [a, b] ⋂ [c, d] ≠ 𝟇

Let’s look at the problem statement:

You are given a set of intervals [ai, biof length N, where i 𝞊 { 1, 2, ….. N }. Now you have to find the maximum number of overlapping intervals.

Let’s understand the problem using an example.

Given a set of intervals,

Input:  N and a  set of intervals of length N,

Intervals = {[0, 2], [3, 7], [4, 6], [7, 8], [1, 5]}

Output:  3

Explanation: The maximum number of overlapping is 3 as

we see that [3, 7], [4, 6], and [1, 5] are the maximum number of intervals that have a non-empty intersection, i.e., [4, 5].

## Approach 1: Naive

First, let’s look at the naive approach that would probably strike anybody’s mind before jumping to an optimal approach.

So, the basic approach considers all subsets of the given set of intervals and then finds the maximum length of the subset with overlapping intervals using the definition mentioned earlier.

So the naive/basic approach could be formulated as:

1. For each subset in the given set of intervals, check if the subset contains only overlapping intervals.
2. If the subset contains only overlapping intervals the maximize the answer.

Now let’s look at the PseudoCode.

### PseudoCode

Algorithm

___________________________________________________________________

procedure MaximumOverlappingIntervals(intervals):

___________________________________________________________________

1.    subsets ← computeSubsets(intervals) #compute all subsets of intervals

2.    maxLength ← 0                       # initially set to 0 in case the intervals size is 0

3.    for subset in subsets do

4.    if containsOverlappingIntervals(subset) == True do

5.     maxLength ← max(maxLength, subset.size())

6.     end if

7.    return maxLength

8.    end procedure

___________________________________________________________________

### C++

``````//C++ program to find the maximum length of Overlapping set
#include <bits/stdc++.h>
using namespace std;
vector<vector<vector<int>>> computeSubsets(vector<vector<int>> &intervals, int N){
vector<vector<vector<int>>> subsets;
// we know that subsets can be represented using an integer
// and there are at most 1<<N subsets
// hence iterating over all integers from 0 to 1<<N
for(int i=0; i<(1<<N); ++i){
vector<vector<int>> v; // current subset
int j = 0; // variable to check if the bit at a position is set in i
while((1<<j)<=i){
if(((1<<j)&i)>0){ // if bit at current position is set in both i and j
v.push_back(intervals[j]); // push it in the current subset
}
j++;      // shift to the next bit
}
if(v.size()>0)      // if the subset is not empty push it
subsets.push_back(v); // in the subsets vector
}
// return the subsets
return subsets;
}
// function which returns the intersection of the given subsets a and b
vector<int> computeIntersection(vector<int> &a, vector<int> &b){
if(!(a<= b and b<= a and a<=b)) return {};
return {max(a, b), min(a, b)};
}
// boolean function that finds whether the set
// of intervals contain the set of Overlapping intervals
bool containsOverlappingIntervals(vector<vector<int>> subset){
sort(subset.begin(), subset.end());
if(subset.size()==1) return 1;
vector<int> intersection = computeIntersection(subset, subset);
if(intersection.size()==0) return false;
for(int i=1;i<subset.size();++i){
intersection = computeIntersection(intersection, subset[i]);
if(intersection.size()==0) return false;
}
return true;
}
// finds the maximum length of Overlapping interval set
int maximumOverlappingIntervals(vector<vector<int>> &intervals, int N){
int maxLength = 0; // maximum length of the Overlapping intervals set
// subsets
vector<vector<vector<int>>> subsets = computeSubsets(intervals, N);
// iterate over all subsets
for(vector<vector<int>> subset : subsets){
// if it contains joint Intervals
if(containsOverlappingIntervals(subset)){
//maximise the length
maxLength = max(maxLength, (int)subset.size());
}
}
// return maxi_length
return maxLength;
}
int main() {

// number of intervals
int N = 5;
vector<vector<int>> v{{0, 2}, {3, 7}, {4, 6}, {7, 8}, {1, 5}};
cout<<"The maximum number of Overlapping intervals is: ";
cout<<maximumOverlappingIntervals(v, N);
return 0;
}``````

### Java

``````import java.util.Arrays;

class Main
{
// Function to find maximum overlapping interval
public static void maximumOverlappingIntervals(int[] arrival, int[] departure)
{
// Find the time when the last interval ends
int time = Arrays.stream(departure).max().getAsInt();

// Create count array initialized with 0
int[] count = new int[time + 2];

// Fill the count array range count using the array index to store time
for (int i = 0; i < arrival.length; i++)
{
for (int j = arrival[i]; j <= departure[i]; j++) {
count[j]++;
}
}

// Keep track of the time when maximum range overlaps
int max_event_tm = 0;

// Find the the maximum element in the count array
for (int i = 0; i <= time; i++)
{
if (count[max_event_tm] < count[i]) {
max_event_tm = i;
}
}
System.out.println("The maximum number of Overlapping intervals is: " + count[max_event_tm]);
}

public static void main(String[] args)
{
int[] arrival = { 0, 3, 4, 7, 1 };
int[] departure = { 2, 7, 6, 8, 5 };

maximumOverlappingIntervals(arrival, departure);
}
}``````

### Python

``````# Function to find maximum overlapping interval
def maximumOverlappingIntervals( arrival,  departure) :
# Find the time when the last interval ends
time = int(max(departure))
# Create count array initialized with 0
count =  * (time + 2)
# Fill the count array range count using the array index to store time
i = 0
while (i < len(arrival)) :
j = arrival[i]
while (j <= departure[i]) :
count[j] += 1
j += 1
i += 1
# Keep track of the time when maximum range overlaps
max_event_tm = 0
# Find the the maximum element in the count array
i = 0
while (i <= time) :
if (count[max_event_tm] < count[i]) :
max_event_tm = i
i += 1
print("The maximum number of Overlapping intervals is: " + str(count[max_event_tm]))

arrival = [0, 3, 4, 7, 1]
departure = [2, 7, 6, 8, 5]
maximumOverlappingIntervals(arrival, departure)``````

Output

``The maximum number of Overlapping intervals is: 3``

### Complexity Analysis

Time Complexity: O((NLogN) *2N)

This is because we are computing all the subsets, and for each subset, we are checking if it contains all disjointed intervals. So to compute the number of subsets, it takes O(2N) time. The maximum length can be N. Sorting the N length subset takes O(NlogN) time. Hence in total, it takes O((NLogN) *2N) time.

Space complexity: O(2N) at the worst case as we are computing all the subsets.

The above algorithm has some loopholes that we need to tackle. The foremost problem is the exponential time complexity the algorithm is taking, and then the space complexity is also worse, i.e., exponential. This gives us the motivation to improve our algorithm.

So let’s think about an efficient approach to solve the problem.

## Approach 2: Efficient

If we want to build up an efficient solution, we will need to find out if there is any redundancy or any repetition that we are doing.

So the redundancy in our above approach is that we find all possible subsets and then check each subset if it has overlapping intervals and update our answer. So we aim to avoid computing all subsets. Hence, we need to make some observations using the definition of overlapping intervals or the repetitive checks in the previous algorithm and infer some important points to simplify our approach.

Let’s look at the overlapping interval definition. We can find that if 2 intervals are overlapping, the endpoint of an interval will occur before the starting point of the next interval.

The crux of the problem lies here, i.e., if we start considering the starting and ending points of an interval as independent elements, we can keep track of how many intervals overlap at a particular stage.

So mark each starting point by the key ‘s’ and an ending point by key ‘e’ so that we can track if it’s a starting or an ending point. It will help us check the overlapping conditions.

Intuition behind Sorting?

The intuition behind sorting is that if we get all points in sorted order, we will maximize our answer while updating the count of overlapping points at a particular stage. So if we get two consecutive points with key ‘s’ in the sorted order, we can easily say that we have 2 overlapping points. This is because if there were non-overlapping points, then the end-point of either starting point would appear before.

(Tip of Advice: get rid of a greedy path as early as possible. If it works and you can think of an intuitive proof then, great; otherwise, you won’t spend time, later on, thinking on a greedy path).

Let’s say the optimal answer by our approach is K -> maximum number of overlapping intervals.

→ There will be K consecutive starting points in the sorted order of the values.

This claim can be easily proved, and it will help us prove the correctness of the greedy algorithm. (It’s left as an exercise for you.)

Let’s formulate our approach.

1. Separate out the starting and ending points of an interval in the form of value, key pair in a single list, and mark the key ‘s’ if it’s a starting point and ‘e’ if it’s an ending point.
2. Sort the above list by values.
3. Maintain a counter to find the number of overlapping intervals at a given stage.
4. Increment the counter if a point has a key ‘s’, else decrement the counter.

### C++

``````//C++ program to find the maximum length of Overlapping set
#include <bits/stdc++.h>
using namespace std;

// custom comparator to sort the interval points vector
bool comp(pair<int, char> &a, pair<int, char> &b){
return a.first <= b.first;
}

// finds the maximum length of Overlapping interval set
int maximumOverlappingIntervals(vector<vector<int>> &intervals, int N){
int maxLength = 0; // maximum length of the Overlapping intervals set

// create another vector which store interval points separately
// in the form of value, key pairs

vector<pair<int, char>> intervalPoints;
for(vector<int> v: intervals){
intervalPoints.push_back({v, 's'});
intervalPoints.push_back({v, 'e'});
}

// sort the interval points by its values
sort(intervalPoints.begin(), intervalPoints.end(), comp);

int counter = 0; // to maintain count of Overlapping intervals at a stage

// iterate over all points
for(int i=0;i<intervalPoints.size();++i){
// if it's a start point increment the counter
if(intervalPoints[i].second=='s'){
counter++;
}else{
counter--;
}

// maximize the length
maxLength = max(maxLength, counter);
}

// return maxi_length
return maxLength;
}

int main() {

// number of intervals
int N = 5;
vector<vector<int>> v{{0, 2}, {3, 7}, {4, 6}, {7, 8}, {1, 5}};
cout<<"The maximum number of Overlapping intervals is: ";
cout<<maximumOverlappingIntervals(v, N);
return 0;
}``````

### Python

``````def overlap(v):

# variable to store the max count
ans = 0
count = 0
data = [] #data vector to store x,y coordinate

for i in range(len(v)):

# appending the x coordinate
data.append([v[i], 'x'])

# appending the y coordinate
data.append([v[i], 'y'])

# sorting of ranges
data = sorted(data)

# Traverse the data vector to
# count number of overlaps
for i in range(len(data)):

# if x occur it means a new range
# is added so we increase count
if (data[i] == 'x'):
count += 1

# if y occur it means a range
# is ended so we decrease count
if (data[i] == 'y'):
count -= 1

# updating the value of ans
# after each traversal
ans = max(ans, count)

# printing the ans (that is maximum value)
print("The maximum number of Overlapping intervals is:", ans)

# Main Function(Driver code)
v = [ [ 0, 2 ], [ 3, 7 ], [ 4, 6 ], [ 7, 8 ], [ 1, 5 ] ]
overlap(v)``````

### Java

``````import java.util.*;
import java.io.*;
import java.lang.*;

class CodingNinjas{

static class pair{
char second;
int first;

pair(int first, char second){
this.second = second;
this.first = first;
}
}

// Function to print maximum overlap
static void overlap(int[][] v){

int ans = 0;
int count = 0;
ArrayList<pair> data = new ArrayList<>();

// Store the x and y coordinates in vector data
for(int i = 0; i < v.length; i++){
}

// Sort the ranges
Collections.sort(data, (a, b) -> a.first-b.first);

// Iterate the data vector for counting the number of overlaps
for(int i = 0; i < data.size(); i++){

// If element is equal to x it means new range is added
if (data.get(i).second == 'x')
count++;

// If element is equal to x it means a range is ended
if (data.get(i).second == 'y')
count--;

ans = Math.max(ans, count);
}

// Print the maximum value
System.out.println("The maximum number of Overlapping intervals is: " + ans);
}

// Driver code
public static void main(String[] args){
int[][] v = {{0, 2}, {3, 7}, {4, 6}, {7, 8}, {1, 5}};
overlap(v);
}
}``````

Output

``The maximum number of Overlapping intervals is: 3``

Time Complexity: O(NLogN)

Since we are sorting the set of intervals of length N, which takes most of the time, it takes O(NLogN) time.

Space complexity: O(N) at the worst case, as the auxiliary space used by the sorting algorithm is O(N).

Hence we reached an efficient solution from an exponential solution.

### Does a greedy algorithm always work?

No, a greedy algorithm does not always work. To solve a problem via a greedy algorithm, you need to have intuitive proof in your mind, at least to lead to the correct solution. To show when it doesn’t work, you can think of a counter-example that will help rule out the greedy algorithm.

### Why is sorting important?

Sorting is a very useful technique because we can reduce a significant number of comparisons. With reference to the question discussed in this blog, we moved from an exponential solution to an O(NLogN) solution. It’s sufficient to explain the power of sorting.

### What is a  comparator?

Comparator is an important concept. It is a function object that helps to achieve custom sorting depending on the problem requirements.

## Conclusion

This article taught us how to find the Maximum number of Overlapping Intervals by approaching the problem using a naive approach followed by an efficient solution. We discussed an iterative implementation using examples, pseudocode, an intuition to our solution, and proper code in detail.

We hope you could take away critical techniques like analyzing problems by walking over the execution of the examples and finding out how we can apply sorting to simplify our task and make fewer comparisons, and how you should approach a greedy solution before writing the code. Testing a greedy algorithm as early as possible is a good practice as there is no guarantee that it will always work. Hence, if it does not work, you could rule it out and not follow a similar approach to solve the problem.

Now, we recommend you practice problem sets based on the concepts of Maximum Disjoint Intervals to master your fundamentals. You can get a wide range of questions similar to the problem Maximum number of Overlapping Intervals on CodeStudio 