Maximum Number of Overlapping Intervals

aniket verma
Last Updated: May 24, 2022
Difficulty Level :
MEDIUM

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[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: 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.
  5. At every stage, maximize your answer.  

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[0], 's'});
        intervalPoints.push_back({v[1], '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][0], 'x'])

		# appending the y coordinate
		data.append([v[i][1], '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][1] == 'x'):
			count += 1

		# if y occur it means a range
		# is ended so we decrease count
		if (data[i][1] == '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++){
        	data.add(new pair(v[i][0], 'x'));
        	data.add(new pair(v[i][1], 'y'));
    	}
     
    	// 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. 

Frequently Asked Questions

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

Was this article helpful ?
1 upvote

Comments

No comments yet

Be the first to share what you think