435. Non-overlapping Intervals

435. 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: 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. Example 1:

Input: [ [1,2], [2,3], [3,4], [1,3] ]Output: 1Explanation: [1,3] can be removed and the rest of

Example 2:

Input: [ [1,2], [1,2], [1,2] ]Output: 2Explanation: You need to remove two [1,2] to make the rest of

Example 3:

Input: [ [1,2], [2,3] ]Output: 0Explanation: You don't need to remove any of the intervals since they're

/** * 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) { if(intervals.length == 0) return 0; Comparator comp = new Comparator() { public int compare(Interval interval1, Interval interval2) { if(interval1.end > interval2.end) return 1; else if(interval1.end < interval2.end) return -1; else return 0; } }; Arrays.sort(intervals, comp); int lastend = intervals[0].end; int remove = 0; for(int i = 1; i < intervals.length; i++) { if(intervals[i].end == lastend) remove++; else if(intervals[i].start < lastend) remove++; else lastend = intervals[i].end; } return

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。