Merge Intervals -- LeetCode

 
這是一道關於interval數組結構的操作，在面試中也是一種比較常見的數據結構。假設這些interval是有序的（也就是說先按起始點排序，然後如果起始點相同就按結束點排序），那麼要把它們合並就只需要按順序讀過來，如果當前一個和結果集中最後一個有重疊，那麼就把結果集中最後一個元素設為當前元素的結束點（不用改變起始點因為起始點有序，因為結果集中最後一個元素起始點已經比當前元素小了）。那麼剩下的問題就是如何給interval排序，在java實現中就是要給interval自定義一個Comparator，規則是按起始點排序，然後如果起始點相同就按結束點排序。整個算法是先排序，然後再做一次線性遍歷，時間復雜度是O(nlogn+n)=O(nlogn)，空間復雜度是O(1)，因為不需要額外空間，只有結果集的空間。代碼如下：

public ArrayList merge(ArrayList intervals) {
    ArrayList res = new ArrayList();
    if(intervals==null || intervals.size()==0)
        return intervals;
    Comparator comp = new Comparator()
    {
        @Override
        public int compare(Interval i1, Interval i2)
        {
            if(i1.start==i2.start)
                return i1.end-i2.end;
            return i1.start-i2.start;
        }
    };
    Collections.sort(intervals,comp);
    
    res.add(intervals.get(0));
    for(int i=1;i=intervals.get(i).start)
        {
            res.get(res.size()-1).end = Math.max(res.get(res.size()-1).end, intervals.get(i).end);
        }
        else
        {
            res.add(intervals.get(i));
        }
    }
    return res;
}