LeetCode刷题——无重叠区间#435#Medium-创新互联

无重叠区间的思路探讨与源码
无重叠区间的题目如下图，该题属于数组类和搜索类型的题目，主要考察对于搜索方法的使用和数组结构的理解。本文的题目作者想到2种方法，分别是双指针方法和贪心方法，其中双指针方法使用Java进行编写，而贪心方法使用Python进行编写，当然这可能不是最优的解法，还希望各位大佬给出更快的算法。

本人认为该题目可以使用双指针方法的思路进行解决，首先将传入的数组进行排序，然后初始化计数参数并计算数组长度，让左右指针分别指向第一个和第二个数组元素，开始遍历循环，判断左指针对应的第二列的元素是否大于右指针对应的第一列的元素，如果是就继续判断左指针对应的元素是否小于右指针对应的元素，如果是就把左指针向左移动一位，如果否就把左指针移动到右指针向左移动一位的位置，把计数参数加1；如果否就把左指针移动到右指针向左移动一位的位置，以此遍历循环直到循环结束并返回最终的计数参数的结果。那么按照这个思路我们的Java代码如下：

#喷火龙与水箭龟
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, new Comparator() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] != o2[0]) {
                    return o1[0] - o2[0];
                }else
                    return o1[1] - o2[1];
            }
        });
        int countNum = 0;
        int numLen = intervals.length;
        int ir = 0;
        int jr = 1;
        for (ir = 0; ir< numLen - 1 && jr<= numLen - 1; ir++,jr++) {
            if (intervals[ir][1] >intervals[jr][0]) {
                if(intervals[ir][1]< intervals[jr][1]){
                    ir = ir -1;
                }else{
                    ir = jr -1;
                }
                countNum = countNum + 1;
            } else {
                ir = jr - 1;
            }
        }
        return countNum;
    }
}

显然，我们的双指针方法的效果一般，还可以用贪心方法进行解决。首先判断数组是否为空，如果是就直接返回0并结束。将数组进行排序，并计算数组的长度，获取数组第一行第二列作为初始值。开始遍历循环，判断数组的元素是否大于初始值，如果是就把结果加1，同时将数组元素赋值给初始值，按照这个思路处理直到遍历结束，并最终返回数组长度减去结果的值。所以按照这个思路就可以解决，下面是Python代码：

#喷火龙与水箭龟
class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) ->int:
        if not intervals:
            return 0
        intervals.sort(key=lambda x: x[1])
        numLen = len(intervals)
        ind = intervals[0][1]
        res = 1
        for ir in range(1, numLen):
            if intervals[ir][0] >= ind:
                res = res + 1
                ind = intervals[ir][1]
        return numLen - res

从结果来说Java版本的双指针方法的效率一般，而Python版本的贪心方法的速度比较不错，但应该是有更多的方法可以进一步提速的，希望朋友们能够多多指教，非常感谢。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧