BiruLyu
7/19/2017 - 11:25 PM

## 435. Non-overlapping Intervals(#).java

``````/**
* 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; }
* }
*/
public class Solution {
public boolean isOverlapping(Interval i, Interval j) {
return i.end > j.start;
}
public int eraseOverlapIntervals(Interval[] intervals) {
if (intervals == null || intervals.length == 0) {
return 0;
}
Arrays.sort(intervals, new Comparator<Interval>() {
public int compare(Interval a, Interval b) {
return a.start - b.start;
}
});
int end = intervals[0].end, prev = 0, count = 0;
for (int i = 1; i < intervals.length; i++) {
if (intervals[prev].end > intervals[i].start) {
if (intervals[prev].end > intervals[i].end) {
prev = i;
}
count++;
} else {
prev = i;
}
}
return count;
}
}``````
``````/**
* 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; }
* }
*/
public class Solution {
public int eraseOverlapIntervals(Interval[] intervals) {
if(intervals.length <= 1) return 0;
Arrays.sort(intervals, new myComparator());
int end = intervals[0].end;
int cnt = 1;
for(int i = 0; i < intervals.length; i++){
if(intervals[i].start >= end){
end = intervals[i].end;
cnt++;
}
}
return intervals.length - cnt;
}
class myComparator implements Comparator<Interval>{
@Override
public int compare(Interval a, Interval b){
return Integer.compare(a.end, b.end);
}
}
}``````
``````/**
* 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; }
* }
*/
public class Solution {
public boolean isOverlapping(Interval i, Interval j) {
return i.end > j.start;
}
public int eraseOverlapIntervals(Interval[] intervals) {
if (intervals == null || intervals.length == 0) {
return 0;
}
Arrays.sort(intervals, new Comparator<Interval>() {
public int compare(Interval a, Interval b) {
return a.start - b.start;
}
});
int dp[] = new int[intervals.length];
dp[0] = 1;
int ans = 1;
for (int i = 1; i < dp.length; i++) {
int max = 0;
for (int j = i - 1; j >= 0; j--) {
if (!isOverlapping(intervals[j], intervals[i])) {
max = Math.max(dp[j], max);
}
}
dp[i] = max + 1;
ans = Math.max(ans, dp[i]);

}
return intervals.length - ans;
}
}``````