Which interval would be the best **first** (leftmost) interval to keep? One that ends first, as it leaves the most room for the rest. So take one with smallest `end`

, remove all the bad ones overlapping it, and repeat (taking the one with smallest `end`

of the remaining ones). For the overlap test, just keep track of the current end, initialized with negative infinity.

## Ruby

Take out intervals as described above, so what's left is the bad overlapping ones, so just return their number.

```
def erase_overlap_intervals(intervals)
end_ = -1.0 / 0
intervals.sort_by(&:end).reject { |i|
end_ = i.end if i.start >= end_
}.size
end
```

Alternatively, `i.start >= end_ and end_ = i.end`

works, too.

## Python

```
def eraseOverlapIntervals(self, intervals):
end = float('-inf')
erased = 0
for i in sorted(intervals, key=lambda i: i.end):
if i.start >= end:
end = i.end
else:
erased += 1
return erased
```