Introduction
In this blog, we will discuss how to find the Maximum Disjoint Intervals. It is an important problem to get a strong grip over greedy algorithms and has also been asked in many interviews.
A common prerequisite is having a basic knowledge of sorting, dp, and how comparators are written. Without knowing this, it is recommended to learn sorting, dp, and comparators. Nevertheless, we’ll try to cover each point in-depth that is required to find the Maximum Disjoint Intervals.
What do we mean by the Disjoint Intervals?
Well, it’s a trivial question, but still, for the sake of clarity, we’ll define that let
Two intervals [a, b], and [c, d] where a <= b and c <= d are said to be disjoint if they do not have any point in common. In the mathematical form, we can write as:
Two intervals [a, b] and [c, d] are said to be disjoint if,,→ a <= b < c <= 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 length of the set of disjoint 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 = {[1, 8], [2, 5], [7, 8]}
Output: 2
Explanation: The maximum set of disjoint intervals is 2 as we see that [2, 5], [7, 8] form the maximum set of disjoint intervals.
Also see, Euclid GCD Algorithm
Approach
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 of disjoint 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 disjoint intervals.
- If the subset contains only disjoint intervals then maximize the answer.
Now let’s look at the PseudoCode.
PseudoCode
Algorithm
___________________________________________________________________
procedure MaximumDisjointIntervals(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 containsDisjointIntervals(subset) == True do
5. maxLength ← max(maxLength, subset.size())
6. end if
7. return maxLength
8. end procedure
___________________________________________________________________CODE IN C++
|
//C++ program to find the maximum length of disjoint 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; }
// boolean function that finds whether the set // of intervals contain the set of disjoint intervals bool containsDisjointIntervals(vector<vector<int>> subset){ sort(subset.begin(), subset.end()); for(int i=0;i<subset.size()-1;++i){ // if intersection is not null if(subset[i][1]>=subset[i+1][0] or subset[i][1]>=subset[i+1][0]){ return false; // this subset doesn't contain disjoint intervals } } return true; }
// finds the maximum length of disjoint interval set int maximumDisjointIntervals(vector<vector<int>> & intervals, int N){ int maxLength = 0; // maximum length of the disjoint 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(containsDisjointIntervals(subset)){ //maximise the length maxLength = max(maxLength, (int)subset.size()); } } // return maxi_length return maxLength; }
int main() {
// number of intervals int N = 3;
vector<vector<int>> v{{1, 8}, {7, 8}, {2, 5}};
cout<<"The maximum length of disjoint interval set is: "; cout<<maximumDisjointIntervals(v, N); return 0; } |
Output
| The maximum length of disjoint interval set is: 2 |
Time Complexity: O((N*logN) *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.
306+ registered