https://leetcode.com/problems/non-overlapping-intervals/

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:

1. You may assume the interval’s end point is always bigger than its start point.
2. Intervals like [1,2] and [2,3] have borders “touching” but they don’t overlap each other.

#### java

https://discuss.leetcode.com/topic/65594/java-least-is-most

Java: Least is Most

Actually, the problem is the same as “Given a collection of intervals, find the maximum number of intervals that are non-overlapping.” (the classic Greedy problem: Interval Scheduling). With the solution to that problem, guess how do we get the minimum number of intervals to remove? : )

Sorting Interval.end in ascending order is O(nlogn), then traverse intervals array to get the maximum number of non-overlapping intervals is O(n). Total is O(nlogn).

https://discuss.leetcode.com/topic/65828/java-solution-with-clear-explain

Java Solution with clear explain

First we sort the array by below rules

Then, visited array by end. If we visited next closest end interval, access the bigger start priority.

https://discuss.leetcode.com/topic/65583/o-nlogn-java-solution

O(nlogn) java solution,

used similar logic to “Merge Inteval” problem in leetcode to solve this problem.

https://discuss.leetcode.com/topic/4319/a-simple-java-solution/2

#### cpp

https://discuss.leetcode.com/topic/65629/concise-c-solution

Concise C++ Solution

#### python

https://discuss.leetcode.com/topic/65672/short-ruby-and-python

Short Ruby and Python

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.

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

Alternatively, i.start >= end_ and end_ = i.end works, too.