Greedy: Remove overlapping intervals.

Problem Statement:

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

Example

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

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

Solution

We follow greedy approach as below:

1. Sort the elements by their end time.

2. Traverse the sorted array and for every interval that fits, increment the counter.

3. Subtract the counter from the length of the array and return the value.

Solution in C++

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>

using namespace std;

int eraseOverlapIntervals(vector<vector<int>>& intervals) 
{
    if(intervals.size()==0) 
      return 0;

    sort(intervals.begin(), intervals.end(), [](vector<int> x, vector<int> y) 
    {
        return x[1]<y[1];
    });

    int remove = 0;
    int j = 0;
    vector<vector<int>> accepted;

    accepted.push_back(intervals.front()); //first interval
    for(int i=1; i<intervals.size(); i++) 
    {
        if(accepted[j][0] < intervals[i][1] && intervals[i][0] < accepted[j][1]) {
            remove++;
        }
        else {
            accepted.push_back(intervals[i]);
            j++;
        }
    }
    return remove;
}


int main()
{
   vector<vector<int>> intervals = {{1,2},{2,3},{3,4},{1,3}};
   cout<<"The intervals to be removed are "<<eraseOverlapIntervals(intervals)<<endl;
   return 0;
}

Output:

The intervals to be removed are 1