435. Non-overlapping Intervals

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.
1
2
3
4
5
6
Example 1:
Input: [ [1,2], [2,3], [3,4], [1,3] ]

Output: 1

Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.
1
2
3
4
5
6
Example 2:
Input: [ [1,2], [1,2], [1,2] ]

Output: 2

Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.
1
2
3
4
5
6
Example 3:
Input: [ [1,2], [2,3] ]

Output: 0

Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

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).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int eraseOverlapIntervals(Interval[] intervals) {
if (intervals.length == 0) return 0;

Arrays.sort(intervals, new myComparator());
int end = intervals[0].end;
int count = 1;

for (int i = 1; i < intervals.length; i++) {
if (intervals[i].start >= end) {
end = intervals[i].end;
count++;
}
}
return intervals.length - count;
}

class myComparator implements Comparator<Interval> {
public int compare(Interval a, Interval b) {
return a.end - b.end;
}
}

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

Java Solution with clear explain

First we sort the array by below rules

1
2
1) sort by end, smaller end in front
2) if end is same, sort by start, bigger start in front

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* 16 / 16 test cases passed
* Status: Accepted
* Runtime: 9 - 10 ms
*
* @param intervals
* @return
*/
public int eraseOverlapIntervals(Interval[] intervals) {
Arrays.sort(intervals, new Comparator<Interval>() {
@Override
public int compare(Interval o1, Interval o2) {
if (o1.end != o2.end) return o1.end - o2.end; //first sort by end
return o2.start - o1.start; //second sort by start
}
});

int end = Integer.MIN_VALUE;
int count = 0;
for (Interval interval : intervals) {
if (interval.start >= end) end = interval.end;
else count++;
}

return count;
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int eraseOverlapIntervals(Interval[] intervals) {
if (intervals == null || intervals.length < 2){
return 0;
}

//sort based on start time of the interval
Arrays.sort(intervals, new Comparator<Interval>(){
@Override
public int compare(Interval e0, Interval e1){
return Integer.compare(e0.start, e1.start);
}
});

int n = intervals.length;
int endLast = intervals[0].end;

int ret = 0;
for (int i = 1; i < n; i++){
int incremental = endLast > intervals[i].start? +1: 0;
endLast = incremental == 1? Math.min(endLast, intervals[i].end): intervals[i].end;
ret += incremental;
}
return ret;
}

cpp


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

Concise C++ Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int eraseOverlapIntervals(vector<Interval>& intervals) {
auto comp = [](const Interval& i1, const Interval& i2){ return i1.start < i2.start; };
sort(intervals.begin(), intervals.end(), comp);
int res = 0, pre = 0;
for (int i = 1; i < intervals.size(); i++) {
if (intervals[i].start < intervals[pre].end) {
res++;
if (intervals[i].end < intervals[pre].end) pre = i;
}
else pre = i;
}
return res;
}
};

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.

1
2
3
4
5
6
7
8
9
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
谢谢你,可爱的朋友。