摘要：題目要求輸入一系列區(qū)間，將出現(xiàn)交叉的區(qū)間合并起來，并將合并后的區(qū)間返回。將這兩個(gè)數(shù)組分別排序可以得到和。也就是說，合并后的結(jié)果和是等價(jià)的。舉個(gè)栗子，輸入為，先判斷是否是獨(dú)立區(qū)間，可見可以和合并，則將修改為。

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

輸入一系列區(qū)間，將出現(xiàn)交叉的區(qū)間合并起來，并將合并后的區(qū)間返回。這里需要注意的是，區(qū)間的大小順序無關(guān)，即輸出為[1,2],[3,4]和[3,4],[1,2]都是可以的

第一次看到這道題目，難免就會(huì)想到，將這些區(qū)間按照開始值有小到大排序，然后依次比較前后兩個(gè)區(qū)間的開始值和結(jié)束值，如果出現(xiàn)重疊，則將兩個(gè)區(qū)間合并。
在這里先介紹一下，java中的兩種利用API進(jìn)行排序的方法。
當(dāng)排序?qū)ο笫菙?shù)組時(shí)，可以使用Arrays.sort機(jī)制，它的核心實(shí)現(xiàn)在于Comparable接口。任何一個(gè)實(shí)現(xiàn)了該接口的數(shù)組中的成員都可以使用Arrays.sort方法。
當(dāng)排序?qū)ο笫羌蠒r(shí)，可以使用list.sort方法。它的核心實(shí)現(xiàn)在于Comparator接口。通過該接口可以實(shí)現(xiàn)集合的排序。
在這里不詳細(xì)介紹這二者的內(nèi)核和具體實(shí)現(xiàn)，有興趣的可以查看java API。
代碼實(shí)現(xiàn)如下：

    public List merge(List intervals) {
        List result = new ArrayList();
        if( intervals.size() == 0){
            return result;
        }
        intervals.sort(new Comparator(){
            @Override
            public int compare(Interval o1, Interval o2) {
                if(o1.start < o2.start){
                    return -1;
                }else if(o1.start > o2.start){
                    return 1;
                }
                
                return 0;
            }    
        });
        
        result.add(intervals.get(0));
        for(int i = 1 ; i previous.end ? temp.end : previous.end;
            }else{
                result.add(temp);
            }
        }
        
        return result;
    }

對(duì)對(duì)象的排序其實(shí)相當(dāng)?shù)挠绊懶屎托阅?。其?shí)這題的問題跳脫出來看，無需知道特定的區(qū)間，只要知道所有的按順序的起始值和終點(diǎn)值。
例如輸入為[1,3],[5,6],[2,7]
如果按照思路一，則需要先將對(duì)象排序，得出[1,3],[2,7],[5,6],然后再依次判斷是否需要合并臨近區(qū)間。
按照思路二，我們直接將區(qū)間看成起始值列表[1,5,2]和結(jié)束值列表[3,6,7]。將這兩個(gè)數(shù)組分別排序可以得到[1,2,5]和[3,6,7]。也就是說，[1,3],[5,6],[2,7]合并后的結(jié)果和[1,3],[2,6],[5,7]是等價(jià)的。
為什么呢？因?yàn)槿绻麅蓚€(gè)區(qū)間重疊，那么這兩個(gè)區(qū)間的一個(gè)結(jié)束值和一個(gè)開始值必然不會(huì)出現(xiàn)在結(jié)果集中，也就是說，我只需要找到這兩個(gè)區(qū)間的一個(gè)最小值和一個(gè)最大值就可以了。如果是n個(gè)區(qū)間重疊，那么只要找這n個(gè)區(qū)間的最小值和最大值就可以了。同理，如果一個(gè)區(qū)間和任何一個(gè)區(qū)間都不會(huì)發(fā)生合并，它的開始值和結(jié)束值就必然會(huì)在排序后兩個(gè)數(shù)組中處于相同下標(biāo)的位置。且其結(jié)果值一定小于下一個(gè)下標(biāo)的開始值。
按照這種思路，實(shí)現(xiàn)的代碼如下：

    public List merge2(List intervals) {
        if(intervals == null || intervals.size() < 2)
            return intervals;
        List res = new ArrayList<>();
        int len = intervals.size();
        int[] starts = new int[len], ends = new int[len];
        for(int i = 0; i < len; i++){
            starts[i] = intervals.get(i).start;
            ends[i] = intervals.get(i).end;
        }
        Arrays.sort(starts);
        Arrays.sort(ends);
        
        int start = starts[0], end = ends[0];
        for(int i = 0; i < len - 1; i++){
            if(ends[i] >= starts[i + 1]){
                end = ends[i + 1];
            }
            else{
                end = ends[i];
                res.add(new Interval(start, end));
                start = starts[i + 1];
                end = ends[i + 1];
            }
        }
        res.add(new Interval(start, end));
        return res;
    }

可以看到，該算法的時(shí)間復(fù)雜度為O(4n)

這個(gè)答案參考了一下高分回答。整理了一下思路如下：
其實(shí)在這里無需對(duì)各個(gè)區(qū)間排序。只需要將需要合并的區(qū)間合并起來即可。如果經(jīng)過判斷是獨(dú)立的區(qū)間，則將該區(qū)間加入結(jié)果集，如果不是獨(dú)立的區(qū)間，則將該區(qū)間合并至后續(xù)的區(qū)間并繼續(xù)判斷下一個(gè)區(qū)間在剩余的區(qū)間中是否是獨(dú)立的區(qū)間。
舉個(gè)栗子，輸入為[1,3],[5,6],[10,11],[2,7]，
先判斷[1,3]是否是獨(dú)立區(qū)間，可見[1,3]可以和[2,7]合并，則將[2,7]修改為[1,7]。
接著判斷[5,6]是否可以合并至后面的區(qū)間，發(fā)現(xiàn)需要將[5,6]與[1,7]合并，合并為[1,7]。
最后，還剩下[10,11]和[1,7]可以先后加入結(jié)果集。
代碼如下：

    public List merge3(List intervals) {
           int size = intervals.size();
            if (size < 2) {
                return intervals;
            }
            
            List result = new ArrayList(size);
            Interval[] array = intervals.toArray(new Interval[size]);
            
            for (int f = 0; f < size; f++) {
                Interval first = array[f];
                boolean add = true;
                for (int s = f + 1; s < size; s++) {
                    Interval second = array[s];
                    if (first.end < second.start || first.start > second.end) {
                        continue;
                    }

                    if (first.start <= second.start) {
                        second.start = first.start;
                    }
                    if (first.end >= second.end) {
                        second.end = first.end;
                    }
                    add = false;
                    break;
                }
                
                if (add) {
                    result.add(first);
                }
            }
            return result;
        }

想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~