Greedy: Non overlapping intervals

Problem Statement:

You are given a 2D array which represents interval.

You need to find the minimum number of interval need to be removed to make the intervals non overlapping.

Example:

Input: intervals[][] = [[1, 2], [2, 3], [3, 4], [4, 5], [1, 3]]

Output: 1

Explanation: By removing [1,3], all the range will be non overlapping 

Solution Explanation:

We will use greedy approach to solve this problem.

Sort the array with the starting values.

Then check if starting point is smaller than the ending point of the previous interval.

Then remove the overlapping interval with greater ending point.

Time Complexity: O(1)
Space Complexity: O(1)

Code Solution

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

int solution(vector<vector<int>>& intervals) 
{
  	int count = 0;
  
    sort(intervals.begin(), intervals.end());

    int end = intervals[0][1];
    for (int i = 1; i < intervals.size(); i++) 
    {

        if (intervals[i][0] < end) 
        {

          	count++;
            end = min(intervals[i][1], end);
        }

        else
            end = intervals[i][1];
    }

    return count;
}

int main() 
{
    vector<vector<int> > intervals = {{1, 2}, {2, 3}, {3, 4}, {4, 5}, {1, 3}};
    cout << solution(intervals) << endl;
}

Output

1