> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/greedy/non-overlapping-intervals.md).

# Non-overlapping Intervals

<https://leetcode.com/problems/non-overlapping-intervals/description/>

> Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
>
> Note:
>
> You may assume the interval's end point is always bigger than its start point.
>
> Intervals like \[1,2] and \[2,3] have borders "touching" but they don't overlap each other.

## Thoughts

<https://en.wikipedia.org/wiki/Interval_scheduling#Interval_Scheduling_Maximization>

## Code

```
/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
class Solution {
    public int eraseOverlapIntervals(Interval[] intervals) {
        int res = 0;
        Arrays.sort(intervals, (a, b) -> a.end - b.end);
        Interval last = null;
        for (Interval interval : intervals) {
            if (last == null || last.end <= interval.start) {
                res++;
                last = interval;
            }
        }
        return intervals.length - res;
    }
}
```

## Analysis

时间复杂度O(nlgn)