Merge interval pattern: Make Intervals Non Overlapping

Problem Statement:

You are given intervals [start, end], return the minimum number of intervals that you need to remove to make the rest of intervals non overlapping.

Example:

Input: arr = [[1, 2], [2, 3], [1, 3]]
Output: 1

Explanation:

You need to remove [1, 3] to make the intervals non overlapping.

Solution Explanation:

We will sort the intervals on the basis of the end points.

We will keep track of the previous end.

Then if the next start > previous end, then remove element.

Time Complexity: O(nlogn)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <unordered_map>
using namespace std;


bool comp(vector<int> &a,vector<int> &b) 
{
	return a[1]<b[1];
}

int solution(vector<vector<int>>& intervals) 
{
	int count = -1;      

	sort(intervals.begin(),intervals.end(),comp); 
	
	vector<int> prev= intervals[0];

	for(vector<int> i: intervals) 
	{
		if(prev[1]>i[0]) 
		{
			count++;
		}
		else 
			prev=i;
	}
	return count;
}

int main() 
{

    vector<vector<int>> intervals = {{1, 3}, {2, 4}, {6, 8}, {9, 11}};

	cout << solution(intervals); 
    return 0;
}

Output

1