## Non-overlapping Intervals

• Time:O(n\log n)
• Space:O(1)

## C++

``````class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
if (intervals.empty())
return 0;

sort(begin(intervals), end(intervals),
[](const auto& a, const auto& b) { return a[1] < b[1]; });

int ans = 0;
int currentEnd = intervals[0][1];

for (int i = 1; i < intervals.size(); ++i)
if (intervals[i][0] >= currentEnd)
currentEnd = intervals[i][1];
else
++ans;

return ans;
}
};
``````

## JAVA

``````class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
if (intervals.length == 0)
return 0;

Arrays.sort(intervals, (a, b) -> a[1] - b[1]);

int ans = 0;
int currentEnd = intervals[0][1];

for (int i = 1; i < intervals.length; ++i)
if (intervals[i][0] >= currentEnd)
currentEnd = intervals[i][1];
else
++ans;

return ans;
}
}
``````

## Python

``````class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
ans = 0
currentEnd = -math.inf

for interval in sorted(intervals, key=lambda x: x[1]):
if interval[0] >= currentEnd:
currentEnd = interval[1]
else:
ans += 1

return ans
``````