無重疊區(qū)間的思路探討與源碼
無重疊區(qū)間的題目如下圖，該題屬于數(shù)組類和搜索類型的題目，主要考察對于搜索方法的使用和數(shù)組結(jié)構(gòu)的理解。本文的題目作者想到2種方法，分別是雙指針方法和貪心方法，其中雙指針方法使用Java進行編寫，而貪心方法使用Python進行編寫，當(dāng)然這可能不是最優(yōu)的解法，還希望各位大佬給出更快的算法。

本人認(rèn)為該題目可以使用雙指針方法的思路進行解決，首先將傳入的數(shù)組進行排序，然后初始化計數(shù)參數(shù)并計算數(shù)組長度，讓左右指針分別指向第一個和第二個數(shù)組元素，開始遍歷循環(huán)，判斷左指針對應(yīng)的第二列的元素是否大于右指針對應(yīng)的第一列的元素，如果是就繼續(xù)判斷左指針對應(yīng)的元素是否小于右指針對應(yīng)的元素，如果是就把左指針向左移動一位，如果否就把左指針移動到右指針向左移動一位的位置，把計數(shù)參數(shù)加1；如果否就把左指針移動到右指針向左移動一位的位置，以此遍歷循環(huán)直到循環(huán)結(jié)束并返回最終的計數(shù)參數(shù)的結(jié)果。那么按照這個思路我們的Java代碼如下：

成都網(wǎng)站建設(shè)哪家好，找成都創(chuàng)新互聯(lián)！專注于網(wǎng)頁設(shè)計、重慶網(wǎng)站建設(shè)公司、微信開發(fā)、小程序開發(fā)、集團成都企業(yè)網(wǎng)站定制等服務(wù)項目。核心團隊均擁有互聯(lián)網(wǎng)行業(yè)多年經(jīng)驗，服務(wù)眾多知名企業(yè)客戶；涵蓋的客戶類型包括：成都混凝土攪拌機等眾多領(lǐng)域，積累了大量豐富的經(jīng)驗，同時也獲得了客戶的一致表揚！

#噴火龍與水箭龜
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;
    }
}

顯然，我們的雙指針方法的效果一般，還可以用貪心方法進行解決。首先判斷數(shù)組是否為空，如果是就直接返回0并結(jié)束。將數(shù)組進行排序，并計算數(shù)組的長度，獲取數(shù)組第一行第二列作為初始值。開始遍歷循環(huán)，判斷數(shù)組的元素是否大于初始值，如果是就把結(jié)果加1，同時將數(shù)組元素賦值給初始值，按照這個思路處理直到遍歷結(jié)束，并最終返回數(shù)組長度減去結(jié)果的值。所以按照這個思路就可以解決，下面是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

從結(jié)果來說Java版本的雙指針方法的效率一般，而Python版本的貪心方法的速度比較不錯，但應(yīng)該是有更多的方法可以進一步提速的，希望朋友們能夠多多指教，非常感謝。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

分享名稱：LeetCode刷題——無重疊區(qū)間#435#Medium-創(chuàng)新互聯(lián)
網(wǎng)頁網(wǎng)址：http://weahome.cn/article/dgeigc.html