## Problem

Problem ID: 435

Title: Non-overlapping Intervals

Difficulty: Medium

Description: Given an array of intervals intervals where intervals[i] = [start_i, end_i], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

## Thoughts

This problem can be reduced to finding longest non-overlapping interval which could be solved greedily.

I like to use the following framework to determine if the problem can be solved greedily. When trying to solve a problem of a smaller size, do we need to choose a less optimal solution to allow for an optimal solution in the future?

If no, the problem can be solved greedily. For the longest non-overlapping interval example, choosing longest non-overlapping interval for the first i interval will not affect the solution for all the intervals.

## Solution

### Implementation

class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {

vector<pair<int,int>> ordered_intervals; // <end, start>
for (const vector<int>& interval : intervals) {
ordered_intervals.push_back({interval[1], interval[0]});
}
sort(ordered_intervals.begin(), ordered_intervals.end());
int next_avail = -INT_MAX;
vector<pair<int,int>> nonoverlap_interval;
for (auto [end, start] : ordered_intervals) {
if (start >= next_avail) {
nonoverlap_interval.push_back({start, end});
next_avail = end;
}
}
return intervals.size() - nonoverlap_interval.size();
}
};