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

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].

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

第一次看到這道題目，難免就會想到，將這些區間按照開始值有小到大排序，然后依次比較前后兩個區間的開始值和結束值，如果出現重疊，則將兩個區間合并。
在這里先介紹一下，java中的兩種利用API進行排序的方法。
當排序對象是數組時，可以使用Arrays.sort機制，它的核心實現在于Comparable接口。任何一個實現了該接口的數組中的成員都可以使用Arrays.sort方法。
當排序對象是集合時，可以使用list.sort方法。它的核心實現在于Comparator接口。通過該接口可以實現集合的排序。
在這里不詳細介紹這二者的內核和具體實現，有興趣的可以查看java API。
代碼實現如下：

    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;
    }

對對象的排序其實相當的影響效率和性能。其實這題的問題跳脫出來看，無需知道特定的區間，只要知道所有的按順序的起始值和終點值。
例如輸入為[1,3],[5,6],[2,7]
如果按照思路一，則需要先將對象排序，得出[1,3],[2,7],[5,6],然后再依次判斷是否需要合并臨近區間。
按照思路二，我們直接將區間看成起始值列表[1,5,2]和結束值列表[3,6,7]。將這兩個數組分別排序可以得到[1,2,5]和[3,6,7]。也就是說，[1,3],[5,6],[2,7]合并后的結果和[1,3],[2,6],[5,7]是等價的。
為什么呢？因為如果兩個區間重疊，那么這兩個區間的一個結束值和一個開始值必然不會出現在結果集中，也就是說，我只需要找到這兩個區間的一個最小值和一個最大值就可以了。如果是n個區間重疊，那么只要找這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;
    }

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

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

    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;
        }

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~