leetcode435无重叠空间

给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。

注意:

可以认为区间的终点总是大于它的起点。
区间 [1,2] 和 [2,3] 的边界相互“接触”,但没有相互重叠。
示例 1:

输入: [ [1,2], [2,3], [3,4], [1,3] ]

输出: 1

解释: 移除 [1,3] 后,剩下的区间没有重叠。
示例 2:

输入: [ [1,2], [1,2], [1,2] ]

输出: 2

解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

思路:为了使删除的数量最下,达到不重叠,那么尽量去删除区间范围大的。

根据区间的后一个值进行排序。那么区间后一个值大的就会被排序到后面。

但是,他们这个数组里的数,就算进行排序后,区间也应该是尽量隔离,并且递增排序的。

for循环判断即可。当第一个值大于后一个值的第一个值,那么删除个数加1.否则,递增下一个即可。

这里贪心的是:以区间后一个值进行排序,贪后一个值过大,导致>它的后一个区间的第一个值。

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if(intervals.length <= 0 || intervals.length == 1)
            return 0;
        
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1]-o2[1];
            }
        });
        int nums = intervals[0][1];
        int numbers = 0;
        
        for(int i = 1;i < intervals.length;i++)
        {    
            if(nums > intervals[i][0])
            {
                numbers++;
                continue;
            }
             nums = intervals[i][1];  
        }
        
        return numbers;
    }
}

 

上一篇:confidence intervals and precision|The One-Mean z-Interval Procedure|When to Use the One-Mean z-Int


下一篇:mysql – 如何向Date_Add添加多个间隔