Problem Statement:
You are given a list of intervals, you need to remove all the intervals that are covered by other intervals and return the number of intervals remaining.
Example
Input: intervals = [[1,4],[3,6],[2,8]]
Output: 2
The interval [3,6] is covered by [2,8], hence can be removed.
Solution
We use greedy approach, we greedily sort the array by its starting time.
If the starting point are same, then we sort by decreasing order of ending time.
Then we compare the end time in the sorted intervals.
If any index ending time is smaller than the current maximum ending point, then that interval is an included one.
Solution in C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<unordered_map>
using namespace std;
bool compare(vector<int>& a, vector<int>& b)
{
if (a[0] != b[0]){
return a[0] < b[0];
}else{
return a[1] > b[1];
}
}
int remove_covered_intervals(vector<vector<int>>& intervals)
{
sort(intervals.begin(), intervals.end(), compare);
int _max = INT_MIN;
int count = 0;
for (int i = 0; i<intervals.size(); i++)
{
if (intervals[i][1] <= _max){
count ++;
}else{
_max = intervals[i][1];
}
}
return intervals.size()-count;
}
int main()
{
vector<vector<int>> intervals = {{1,4},{3,6},{2,8}};
cout<<"The remaining intervals after removing overlapping intervals are "<< remove_covered_intervals(intervals)<<endl;
return 0;
}
Output:
The remaining intervals after removing overlapping intervals are 2