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 are [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, bi ] of 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].
Recommended: Try the Problem yourself before moving on to the solution
Also see, Euclid GCD Algorithm
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:
- For each subset in the given set of intervals, check if the subset contains only overlapping intervals.
- If the subset contains only overlapping intervals 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[0]<= b[0] and b[0]<= a[1] and a[1]<=b[1])) return {};
return {max(a[0], b[0]), min(a[1], b[1])};
}
// 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[0], subset[1]);
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 = [0] * (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: 3Complexity 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.
34+ registered 
