- Non-overlapping Intervals
原创
wx62ea2466cca9a博主文章分类:leetcode ©著作权
文章标签 LeetCode i++ 文章分类 Hadoop 大数据
©著作权归作者所有:来自51CTO博客作者wx62ea2466cca9a的原创作品,请联系作者获取转载授权,否则将追究法律责任
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
- 赞
- 收藏
- 评论
- *举报
上一篇:452. Minimum Number of Arrows to Burst Balloons
Original: https://blog.51cto.com/u_15740726/5541997
Author: wx62ea2466cca9a
Title: 435. Non-overlapping Intervals
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/508375/
转载文章受原作者版权保护。转载请注明原作者出处!