## 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();
}
};
```